CF1548B Integers Have Friends

洛咕

题意：

给定 \(n\) 和一个长度为 \(n\) 的数组 \(a\)，求一个最长的区间 \(\left[l,r\right]\)，使得存在 \(m\geq 2\) 和 \(k\)，对于所有 \(l\leq i\leq r,a_i\equiv k\pmod{m}\)（即区间内所有数对 \(m\) 取模余数相等），输出最长区间长度（区间长度定义为 \(r-l+1\)）。

分析：

最大公约数也具有区间可并性。因此构建ST表，设\(f[i][j]\)表示\(i\) ~ \(i+\)\(2^j\)\(-1\)这段区间的最大公约数，预处理和维护都是模板，然后枚举长度可以用二分答案，时间复杂度约为\(nlog_2\)\(nlog_2\)\(n\).

#include<bits/stdc++.h>

#define ll long long

#define rg register

#define rep(i,j,k) for(int i=j;i<=k;++i)

using namespace std;

inline ll read(){

    char ch=getchar();ll x=0,f=1;

    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}

	while('0'<=ch&&ch<='9'){x=1ll*x*10+ch-'0';ch=getchar();}

	return x*f;

}

const int mod=100003;

const int N=2e5+5;

ll n,a[N],b[N],f[N][21],lg[N];

ll gcd(ll x,ll y){

	if(!y)return x;

	return gcd(y,x%y);

}

ll query(ll l,ll r){

	ll x=lg[r-l+1];

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

}

bool check(ll mid){

	for(int i=1;i+mid-1<=n;++i){

		if(query(i,i+mid-1)>=2)return 1;

	}

	return 0;

}

int main(){

	int T=read();

	while(T--){

		n=read();

		for(int i=1;i<=n;++i)a[i]=read();

		n--;

		for(int i=1;i<=n;++i)b[i]=f[i][0]=abs(a[i]-a[i+1]);

		for(int j=1;j<=20;++j){

			for(int i=1;i+(1<<j)-1<=n;++i){

				f[i][j]=gcd(f[i][j-1],f[i+(1<<(j-1))][j-1]);

			}

		}

		lg[0]=-1;for(int i=1;i<=n;++i)lg[i]=lg[i>>1]+1;

		int l=1,r=n,mid,ans=1;

		while(l<=r){

			mid=(l+r)>>1;

			if(check(mid))l=mid+1,ans=mid+1;

			else r=mid-1;

		}

		cout<<l<<endl;

	}

	return 0;

}

巴特西

CF1548B Integers Have Friends

洛咕

题意：

分析：

最新文章

热门文章