https://codeforces.com/contest/1549/problem/D

昨天晚上在外面完，第一眼想到线段树的例题，看到有人用st表写，先记录一下，马上要打牛客了

基础  https://www.cnblogs.com/ZYBGMZL/p/7270885.html

应该吧RMQ里的max换成—_gcd()就行了

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 200010, M = 18;

int n, m;
int w[N];
int f[N][M];
//int fmin[N][M];
int gcd(int a,int b){  return b==0?a:gcd(b,a%b);  }
void init()
{
    for (int j = 0; j < M; j ++ )
        for (int i = 1; i + (1 << j) - 1 <= n; i ++ )
            if (!j)
            {
                f[i][j] = w[i];
                //fmin
            }
            else 
            {
                f[i][j] = gcd(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
                //fmin
            }
}

int query(int l, int r)
{
    int len = r - l + 1;
    int k = log(len) / log(2);

    return gcd(f[l][k], f[r - (1 << k) + 1][k]);
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    init();

    scanf("%d", &m);
    while (m -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", query(l, r));
    }

    return 0;
}

AC代码

#include<bits/stdc++.h>
using namespace std;

const int N = 200010, M = 18;

int n, m;
long long w[N];
long long f[N][M];
long long a[N];

long long gcd(long long  a,long long b){  return b==0?a:gcd(b,a%b);  }

long long query(int l, int r)
{
    int len = r - l + 1;
    long long k = log(len) / log(2);

    return gcd(f[l][k], f[r - (1 << k) + 1][k]);
}


void slove()
{
//  memset(w,0,sizeof w);
//  memset(f,0,sizeof f);
//  memset(a,0,sizeof a);  试了一下，加了超时 
    int n;
    cin>>n;

    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<n;i++)
    {
        w[i]=abs(a[i+1]-a[i]);
    }


    n--;
    for (int j = 0; j < M; j ++ )
        for (int i = 1; i + (1 << j) - 1 <= n; i ++ )
            if (!j)
            {
                f[i][j] = w[i];
            }
            else 
            {
                f[i][j] = gcd(f[i][j - 1], f[i + (1 << j - 1)][j - 1]); 
            }


    int ans=0,r=1;
    for(int l=1;l<=n;l++)//双指针 l ~ r 
    {
        r=max(r,l);

        while(r+1<=n&&query(l,r+1)>1)
        {
            r++;

        }
        if(r==l&&w[l]==1) continue;
        ans=max(ans,r-l+1);

    }
    cout<<ans+1<<endl;

}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        slove();
    }
    return 0;
}