CF1614D2 Divan and Kostomuksha (hard version)

pengyule · 2021-11-29 15:16:39 · 题解

重排数组 a(n\le 10^6,a_i\le 2\cdot 10^7)，使 \sum_{i=1}^n\gcd(a_1,a_2,...,a_i) 最大化，输出最大值。

这很像一个 DP。我们会发现随着 i 的增大， q_i=\gcd(a_1,a_2,...,a_i) 的变化应该是有 q_i\mid q_{i-1}。那么设 f_i 表示数 i 作为 q 的结末，最大的所求值。于是 {f_i}\gets \max_{i|j}\{f_j+i\cdot(cnt_i-cnt_j)\}，其中 cnt_i 表示 a 中有多少个数是 i 的倍数。

考虑如何计算 cnt_i。一个十分巧妙的方法是从小到大枚举值域内的所有质数（p），并将当前的 cnt_i 加给 cnt_{i\div p}。由于枚举的有序性可以有效地避免进行容斥。（注：初始时只处理出 cnt_{a_i}。）

考虑如何优化 f_i 的求解，因为这样是欧拉筛的复杂度。发现只有当 \frac{j}{i} 为质数时才是有必要的，不然一定可以通过多次为质数的更新替代（矛盾）。这样我们从所有数都要枚举变成了只需要枚举质数，复杂度大幅减少，可以通过。

数论方面的复杂度我不会分析，请高人指点。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,M=2e7;
int n,m,ans,x,a[N],cnt[M+5],f[M+5],v[M+5],prime[M+5];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        cnt[a[i]]++;
    }
    for(int i=2;i<=2e7;i++){
        if(!v[i])prime[++m]=i;
        for(int j=1;j<=m&&i*prime[j]<=2e7;j++){
            v[i*prime[j]]=prime[j];
            if(i%prime[j]==0)break;
        }
    }
    for(int i=1;i<=m;i++)
        for(int j=2e7/prime[i];j;j--)cnt[j]+=cnt[j*prime[i]];
    for(int i=2e7;i;i--){
        if(!cnt[i])continue;
        f[i]=i*cnt[i];
        for(int j=1;j<=m&&i*prime[j]<=2e7;j++)f[i]=max(f[i],f[i*prime[j]]+(cnt[i]-cnt[i*prime[j]])*i);
        if(ans<f[i])ans=f[i],x=cnt[i];
    }
    cout<<ans+n-x;
}