BZOJ-4052: [Cerc2013]Magical GCD

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;
}