自动搬运

查看原文

来自洛谷，原作者为

	redegg K-ON ! ! !

搬运于2025-08-24 22:11:25，当前版本为作者最后更新于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;
}