BZOJ4488 JSOI2015最大公约数

时间：2021-08-17 11:54:21

　　显然若右端点确定，gcd最多变化log次。容易想到对每一种gcd二分找最远端点，但这样就变成log^3了。注意到右端点右移时，只会造成一些gcd区间的合并，原本gcd相同的区间不可能分裂。由于区间只有log个，暴力即可。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define N 100010

#define ll long long

ll read()

{

    ll x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,r[N],tmp[N],head=,tail;

ll a[N],ans,g[N];

ll gcd(ll n,ll m){return m==?n:gcd(m,n%m);}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4488.in","r",stdin);

    freopen("bzoj4488.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read();

    for (int i=;i<=n;i++) a[i]=read();

    for (int i=;i<=n;i++)

    {

        r[++tail]=i;g[tail]=a[i];

        for (int j=head;j<tail;j++) g[j]=gcd(g[j],a[i]);

        int x=tail+;

        for (int j=tail;j>=head;j--)

        {

            int t=j;

            while (t>head&&g[t-]==g[j]) t--;

            x--,r[x]=r[t],g[x]=g[t];

            j=t;

        }

        head=x;

        for (int j=head;j<=tail;j++) ans=max(ans,(i-r[j]+)*g[j]);

    }

    cout<<ans;

    return ;

}

相关文章