题意
给定数组(A(a_1,a_2,a_3....a_n))，求一个最大的连续子数组，子数组满足以下条件
- 模(m(m>1)) 得到的余数相等
分析
假设子数组((a_{i},a_{i+1},a_{i+2}....a_{j})) 模(m)都等于(x)，那么它的差分数组((a_{i+1}-a_{i},a_{i+2}-a_{i+1},a_{i+3}-a_{i+2}....a_j-a_{j-1}))模(m)都等于0
由此可以转化题目为，对于给定数组(A)的差分数组(B(a_2-a_1,a_3-a_2,a_4-a_3.....a_n-a_{n-1}))求最大公约数不为1的最长连续子数组。
我尝试使用线段树来求解，发现超出内存。改用倍增的方法，得到(B)中每个以(l)为起点长度为(2^x)的子数组的最大公约数(f[x][r])。
注意到，求区间([l,r])的最大公约数，可以变成求两区间([l,a])，([b,r])的最大公约数，其中(b)满足(lleq bleq (a+1))
AC代码
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
#define per(i,a,b) for (int i=(b);i>=(a);i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef vector<int> VI;
typedef pair<int,int> PII;
const ll mod=998244353 ;
const int maxn=2e5+7;
ll a[maxn],b[maxn],f[maxn][22];
int n;
ll _gcd(ll a,ll b){
return b ? _gcd(b,a%b) : a;
}
ll check(int l,int r){
int x=log2(r-l+1);
return _gcd(f[l][x],f[r-(1<<x)+1][x]);
}
int main() {
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
rep(i,1,n){
scanf("%lld",&a[i]);
}
rep(i,2,n){
b[i-1]=abs(a[i]-a[i-1]);
f[i-1][0]=b[i-1];
}
rep(i,1,20){
rep(j,1,n-1){
if(j+(1<<i)-1<=n-1)f[j][i]=_gcd(f[j][i-1],f[j+(1<<(i-1))][i-1]);
}
}
int ans=1,l=1;
rep(r,1,n-1){
while(l<r&&check(l,r)==1)l++;
if(check(l,r)!=1)ans=max(ans,r-l+2);
}
printf("%d
",ans);
}
return 0;
}