CF1548B Integers Have Friends (c++)

我们对原数组a前后两项做差并取绝对值，得到新数组b。

b[i]=abs(a[i+1]-a[i]);

那么如果a[l]~a[r]是好的，b[l]|m,b[l+1]|m…b[r-1]|m。因为这里m有就行那么我们钦定m就是这些数的gcd，那么gcd(b[l],b[l+1]…b[r-1])>1就说明区间是好的，用ST表(线段树)维护区间gcd。

找答案的时候枚举右端点，左端点从上一次开始，直到gcd>1。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int T,n,a[N],b[N],mx[N][35];
int f(int l,int r){
int len=r-l+1;
int d=__lg(len);
return __gcd(mx[l][d],mx[r-(1<<d)+1][d]);
}
signed main(){
scanf("%lld",&T);
while(T–){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
for(int i=1;i<n;i++){
b[i]=abs(a[i+1]-a[i]);
mx[i][0]=b[i];
}
for(int i=1;i<=20;i++){//ST表维护区间gcd
for(int j=1;j+(1<<i)-1<=n;j++){
mx[j][i]=__gcd(mx[j][i-1],mx[j+(1<<(i-1))][i-1]);
}
}
int j=1,ans=1;//左端点
for(int i=1;i<n;i++){//右端点
while(j<=i&&f(j,i)==1) j++;//gcd不大于1(也就是等于1)，左端点就还要加
ans=max(ans,i-j+2);//注意要加2，因为差分数组会忽略b[i](也就是最右边的那个数)
}
printf("%lld\\n",ans);
}
return ~(-1);
}