BZOJ4052: [Cerc2013]Magical GCD 暴力+RMQ

题解：

考虑以某个元素开头的前缀gcd，至多只有log段。

这是因为每一次gcd发生变化必然是原来答案的一个真约数，那么最多只有原来的一半。

所以枚举起点不断二分找出所有段即可。

利用RMQ预处理求区间的gcd，每次可以$O(1)$。

于是时间复杂度$O(nlog^2n)$。

然而事实上，我们直接暴力维护所有段即可，因为每次只需要将末尾添加一个数，且只有log段，暴力判断即可。这样就能做到$O(nlogn)$。

我脑洞也是大了点。。。

代码：

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
inline ll gcd(ll a,ll b){
	return(!b)?a:gcd(b,a%b);
}

#define N 100010
ll f[N][17];
int len[N];

inline ll query(int l,int r){
	return gcd(f[l][len[r-l+1]],f[r-(1<<len[r-l+1])+1][len[r-l+1]]);
}
int main(){
#ifndef ONLINE_JUDGE
	freopen("tt.in","r",stdin);
#endif
	int T,n,i,j;
	cin>>T;
	for(i=2;i<=100000;++i)
		len[i]=len[i>>1]+1;
	int L,R,mid;
	while(T--){
		scanf("%d",&n);
		for(i=1;i<=n;++i)
			scanf("%lld",&f[i][0]);
		for(j=1;(1<<j)<=n;++j)
			for(i=1;i+(1<<j)-1<=n;++i)
				f[i][j]=gcd(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		ll ans=0,beg;
		for(i=1;i<=n;++i){
			j=i;
			while(j<=n){
				for(beg=query(i,j),L=j,R=n;L<R;){
					mid=(L+R+1)>>1;
					if(query(i,mid)!=beg)
						R=mid-1;
					else
						L=mid;
				}
				ans=max(ans,beg*(L-i+1));
				j=L+1;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}