题解 P5502 【[JSOI2015]最大公约数】

redegg · 2019-09-20 19:23:54 · 题解

简单证明一下，集合\{gcd(a[l],a[l+1]...a[r])\ | l\le r\}元素个数不超过logn个：

小于n且能被n整除的最大的数字一定小于等于n/2，也就说小于n的最大的gcd不超过n/2。

那么固定r后，每次往左边扩大一格，扩大区间范围后的gcd要么等于原来的gcd，要么就是小于等于原来的gcd/2。也就说产生的新的gcd数值一定都小于等于原来都一半，那么也就最多产生log级别个新的gcd数值。

并且我们发现，左边的gcd(a[l]...a[r])一定小于等于gcd(a[l+1]...a[r])。

所以我们枚举r，用一个队列存储这log个不同的gcd的左端点，每次直接枚举这些gcd更新，更新的时候加一些判断处理重复就好了，写起来很容易。

复杂度：(nlog^2n)

#include <bits/stdc++.h>
using namespace std;

int n;
queue<int> que;
queue<int> lins;
long long g[100005];
long long ans;

long long gcd(long long a,long long b){
    if(a==0)return b;
    return gcd(b%a,a);
}

int main()
{
    scanf("%d",&n);
    g[0]=-1;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&g[i]);
        int last=0;
        while(!que.empty())
        {
            int x=que.front();
            que.pop();
            g[x]=gcd(g[x],g[i]);
            ans=max(ans,g[x]*(i-x+1));
            if(g[x]==g[last])continue;
            lins.push(x);
            last=x;
        }
        ans=max(ans,g[i]);
        while(!lins.empty())
        {
            que.push(lins.front());
            lins.pop();
        }
        if(g[last]!=g[i])que.push(i);
    }
    printf("%lld\n",ans);
    return 0;
}