P4411 [BJWC2010] 取数游戏 题解

· · 题解

题目传送门

博客园 可能食用更佳。

给定 n 个数 a_{1,2,\dots,n}，你需要从左到右按顺序取出一些数，第一个数任取，钦定目前取的数为 a_j，下一个取的数为 a_k，需满足 \gcd(a_j,a_k) \geq L，求最大化取出数的数量。

钦定 V 为 a_i 的最大值，记 f_j 表示约数为 j 时最大的答案数量，每次 \mathcal O(\sqrt a_i) 枚举 a_i 的约数，将 \geq L 的数取出来更新答案即可，最终答案即为 \max_{j=L}^{V} f_j，时间复杂度为 \mathcal O(n \sqrt V)，空间复杂度为 \mathcal O(V)。

const int N=5e4+5,M=1e6+5;
int n,lim,f[M];
vector<int> a[N];
int main()
{
    read(n),read(lim);
    for(int i=1;i<=n;i++)
    {
        int x; read(x);
        for(int j=1;j*j<=x;j++)
            if(x%j==0)
            {
                if(j>=lim) a[i].pb(j);
                if(j*j!=x&&x/j>=lim) a[i].pb(x/j);
            }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int res=0;
        for(auto x:a[i]) chkmax(res,f[x]+1);
        chkmax(ans,res);
        for(auto x:a[i]) f[x]=res;
    }
    write(ans);
    return 0;
}