P5502 [JSOI2015]最大公约数

不具有可减性的区间问题可以试着考虑分治。

设当前区间是 ([l,r])，令 (mid=lfloorfrac{l+r}{2} floor)，递归 ([l,mid-1]) 和 ([mid+1,r]) 求解，然后考虑经过 (mid) 的答案，显然不会少算。

考虑枚举 ([l,mid]) 作为左端点的答案和 ([mid,r]) 作为右端点的答案，当另一端可以无代价拓展时就进行拓展。

这样可能会漏掉一些情况，假设 ([i,j]) 满足 (gcd(a_i,a_{i+1},cdots,a_{mid})=p)，(gcd(a_{mid},cdots,a_{j-1},a_j)=q)。

当 (gcd(p,q)>1) 时一定会漏掉。不过此时我们发现 (2 imesgcd(p,q)leqmin{p,q})，也就是说只要计算了 ([i,mid]) 和 ([mid,j]) 的答案就无须再算 ([i,j]) 的答案，因为较长的那个区间的答案不会更劣。

而这两者肯定都是算过的（可能无代价拓展过），所以正确性没有问题。

时间复杂度 (O(Nlog Nlog A))。

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define Max(x,y)((x)>(y)?x:y)
#define For(i,x,y)for(i=x;i<=(y);i++)
ll a[100005];
ll gcd(ll _,ll __)
{
	return(!_?__:gcd(__%_,_));
}
ll solve(int l,int r)
{
	if(l>r)return 0;
	ll w,ret,tmp;
	int mid=(l+r)>>1,i,j;
	i=j=mid;
	ret=w=a[mid];
	while(l<=i)
	{
		while(j<r&&!(a[j+1]%w))j++;
		ret=Max(ret,w*(j-i+1));
		w=gcd(w,a[--i]);
	}
	i=j=mid;
	w=a[mid];
	while(j<=r)
	{
		while(i>l&&!(a[i-1]%w))i--;
		ret=Max(ret,w*(j-i+1));
		w=gcd(w,a[++j]);
	}
	tmp=solve(l,mid-1);
	ret=Max(ret,tmp);
	tmp=solve(mid+1,r);
	return Max(tmp,ret);
}
int main()
{
	int n,i;
	scanf("%d",&n);
	For(i,1,n)scanf("%lld",&a[i]);
	printf("%lld",solve(1,n));
	return 0;
}