[文章目录]
Description
给出一个长度在 100 000 以内的正整数序列，大小不超过 10^12。求一个连续子序列，使得在所有的连续子序列中，它们的GCD值乘以它们的长度最大。
神题！请收下我的膝盖；
以r结尾区间不同的gcd只有log个，并且他们随l递增而递增。对于最长区间长度只需要记录相同gcd区间最小的l，维护区间的不同的gcd和l。当右端点移动，每个区间右端点多一个数，发现每段区间的gcd都会和该数取gcd，并且gcd相同的以l开头的区间gcd仍然相同。暴力修改gcd，再将相同gcd的区间合并。发现复杂度仍然很对，然而并没有用到任何套路。点个赞；
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll ans,w[101000],gc[101000];
int n,z[101000],b[101000],top;
ll gcd(ll x,ll y){return !y?x:gcd(y,x%y);}
int main()
{
int t; scanf("%d",&t);
while(t--)
{
scanf("%d",&n); ans=top=0;
for(int i=1;i<=n;++i) scanf("%lld",w+i);
for(int i=1;i<=n;++i)
{
for(int j=1;j<=top;++j)
gc[j]=gcd(gc[j],w[i]);
gc[++top]=w[i]; z[top]=i;
int tmp=1; b[1]=1;
for(int j=2;j<=top;++j)
if(gc[j]!=gc[j-1]) b[++tmp]=j;
for(int j=1;j<=tmp;++j)
{
z[j]=z[b[j]]; gc[j]=gc[b[j]];
ans=max(ans,(ll)(i-z[j]+1)*gc[j]);
}
top=tmp;
}
printf("%lld\n",ans);
}
return 0;
}