A50540.gcd 题解

思考一个问题：已知一个 $g$，那么能否快速判断是否有子序列，让其最大公约数为 $g$？容易想到计算所有 $g$ 的倍数的最大公约数 $g'$，再判断 $g'$ 是否等于 $g$ 即可。$g$ 可以枚举得到。显然，$a_i \leq 5000$，所以 $g$ 最多是 $5000$ 而且卡不满，这样我们就解决了如何选择子序列。

而且，选择所有 $g$ 的倍数作为子序列是最优的（比较简单不再赘述）。此时，子序列的最大公约数应该是 $g+1$，非子序列中的最大公约数直接计算即可。最后取最大值。

虽然 $\gcd$ 带有一只 $\log$ 有概率超时，但是刚才说了，$g$ 是卡不满的，所以不用担心。

时间复杂度：卡不满的 $O(n^2 \log n)$.

空间复杂度：$O(n)$.

Code:

#include<bits/stdc++.h>
using namespace std;
int n,g,gg,ans;
int a[5005];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=5000;i++){
        g=0;
        for(int j=1;j<=n;j++){
            if(a[j]%i) continue;
            g=__gcd(a[j],g);
        }
        if(i==g){
            gg=0;
            for(int j=1;j<=n;j++){
                if(a[j]%i) gg=__gcd(a[j],gg);
                else gg=__gcd(g+1,gg);
            }
            ans=max(gg,ans);
        }
    }
    cout<<ans;
    return 0;
}