【JZOJ3780】Magical GCD

Description

对于一个由正整数组成的序列， Magical GCD 是指一个区间的长度乘以该区间内所有数字的最大公约数。给你一个序列，求出这个序列最大的 Magical GCD。

Solution

暴力做法是枚举左端点右端点求最大值。

现在考虑另一种暴力，我们先枚举一个右端点，设$g_i$表示$[i,r]$的$gcd$是什么。那么随着$r$的增大，$g_i$一定单调不上升。

于是我们每次把$r$增加的时候就更新$g_i$的值，然后求最大值即可。

然而有没有优化呢？

我们发现，$g_i$会有很多重复，且重复是连续的。其实$g_i$最多只有$log_2(max\{a_i\})$个取值（其实远远不到），那么对于重复的只要保留第一个即可。

下面感性证明一下$g_i$不同的取值，我们假设有一个集合$\{a\}$，一开始只有一个很大的数，第$i$次有一个数$p$，然后集合增加一个$gcd(p,a_{i-1})$的数。现在我们要让集合大小最大，也就是$a_i=\frac{1}{2}a_{i-1}$，那么长度最多是$log_2a_1$。

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define N 100001
#define ll long long
using namespace std;
ll a[N];
ll gcd(ll x,ll y)
{ll z;while(x%y){z=x%y;x=y;y=z;}return y;
}
ll g[N];
int nx[N],ls[N];
int main()
{int T;cin>>T;while(T--){int n;scanf("%d",&n);fo(i,1,n) scanf("%lld",&a[i]),g[i]=a[i];fo(i,1,n) nx[i]=i+1,ls[i]=i-1;ll ans=0;fo(r,1,n)for(int i=1;i<=r;i=nx[i]){ll t=gcd(g[i],a[r])*(r-i+1);if(ans<t) ans=t;g[i]=gcd(g[i],a[r]);if(g[i]==g[ls[i]]){nx[ls[i]]=nx[i];ls[nx[i]]=ls[i];}}printf("%lld\n",ans);}
}