【二分+ST表】代码源每日一题div2 最长同余子数组

小咪咪 2024-03-16 18:34 34阅读 0赞

[最长同余子数组 - 题目 - Daimayuan Online Judge][- _ - Daimayuan Online Judge]

题意:

![d06c0e4344b14b7f8a54cc848e1bf098.png][]

思路：

注意到，长度越长，越不能同余，因此我们去二分这个长度，然后去check

在check时，如果一个区间的gcd不为1，说明就是合法的，如果不存在这样的区间，那么就是不合法的

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    
    int N;
    int a[mxn];
    int F[mxn][33],lg[mxn];
    
    int query(int l,int r){
    	int k=lg[r-l+1];
    	return __gcd(F[l][k],F[r-(1<<k)+1][k]); 
    }
    bool check(int len){
    	for(int l=1;l+len-1<=N;l++){
    		int r=l+len-1;
    		if(query(l,r)!=1) return true;
    	}
    	return false;
    }
    void LG_init(){
    	lg[1]=0;
    	for(int i=2;i<mxn;i++) lg[i]=lg[i>>1]+1;
    }
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N;i++) cin>>a[i];
    	for(int i=1;i<=N-1;i++){
    		F[i][0]=abs(a[i]-a[i+1]);
    	}
    	for(int j=1;j<=30;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]);
    		}
    	}
    	int l=0,r=N;
    	int ans=1;
    	while(l<=r){
    		int mid=(l+r)>>1;
    		if(check(mid)){
    			ans=mid;
    			l=mid+1;
    		}else r=mid-1;
    	}
    	cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;//cin>>__;
    	LG_init();
    	while(__--)solve();return 0;
    }

[- _ - Daimayuan Online Judge]: http://oj.daimayuan.top/problem/808
[d06c0e4344b14b7f8a54cc848e1bf098.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/96ac2b4966a54ad4bfaa272a48deb33e.png