题解|#F. Array Stabilization (GCD version)# cf

本题暴力循环是使不得的，本人亲测。

首先分析得到，n个数进行gcd操作的结果就是最终的相同的数（自行举几个例子就可以得出这个结论）。

我们注意到转换的步骤有几次，i就和他后面几个数进行gcd操作，而操作次数一定是单调的，所以可以采用二分来优化。

二分出操作次数后，就进行区间查询的操作，在[i,i+mid]区间中进行查询，高效的静态区间查询的数据结构可以采用st表来处理，每次查询的复杂度是o（1），非常优秀。

查询每个区间是否与最终相同的数相同，如果不同，说明区间太小，无法gcd到相同的数，就l=mid+1。

#include<bits/stdc++.h>
using namespace std;
const int M=2e5+5;
int a[M<<1];
int st[M<<1][21];
int n;
int g;
int gcd(int a,int b){
	int r=a%b;
	while(r){
		a=b; b=r; r=a%b;
	}
	return b;
}
int getGcd(int l,int r){
	int k=log2(r-l+1);
	return gcd(st[l][k],st[r-(1<<k)+1][k]);
}
bool check(int x){
	for(int i=1;i<=n;i++){
		if(g!=getGcd(i,i+x)) return 0;
	}
	return 1;
}
int main(){
	int t; cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			a[i+n]=a[i];
			if(i==1) g=a[i];
			else g=gcd(g,a[i]);
		}
	//	cout<<"dao"<<endl;
		for(int i=1;i<=2*n;i++) st[i][0]=a[i]; 
		for(int j=1;j<=20;j++){
			for(int i=1;i<=2*n;i++){
				if(i+(1<<j)-1<=2*n)
					st[i][j]=gcd(st[i][j-1],st[i+(1<<(j-1))][j-1]);
			}
		}
		int l=0; int r=n-1;
	//	cout<<"dao"<<endl;
		while(l<r){
	//		cout<<"1"<<endl;
			int mid=(l+r)>>1;
			if(check(mid)){
				r=mid;
			}
			else{
				l=mid+1;
			}
		}
		cout<<l<<'\n';
	}
	return 0;
}