D1. Divan and Kostomuksha (easy version)

题意：$$\sum_{i=1}^{n} gcd(a_1,a_2,… a_i)$$
的最大值是多少。其中$1 \le a_i \le 2 \times 10^5$ 。

分析：
用$cnt[i]$表示所有数中包含$i$因子的数量，$dp[i]$表示以$i$作为最大$gcd$时贡献的最大值，因为题目要求计算一种排序，使得其贡献值最大。那么我们可以使用一种$dp$的做法，首先统计每个$cnt$的数量预处理一遍，然后$dp[i]$下标从$1$开始跑到$N$，表示当$gcd$为$i$时贡献值为多少然后用一个$MA$每次更新，那么最后跑出来的$MA$即是最佳的一种排序方案使得贡献值最大。

• 代码+注解：

#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long 
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define lowbit(x) (x&-x)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=5e6+10;
int s[N];
int cnt[N];
int dp[N];
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        cnt[x]++;
    }
    for(int i=1;i<N;i++){//这步操作统计拥有因子为i的数有几个(cnt[i]<=n)，复杂度O(nlogn)
        for(int j=i+i;j<N;j+=i){
            cnt[i]+=cnt[j];
        }
    }
    int MA=0;
    dp[1]=cnt[1];//因为每个数必包含因子1，所以dp[1]初始值就是cnt[1]
    for(int i=1;i<N;i++){
        for(int j=i+i;j<N;j+=i){//进行转移，表示确定dp[i]的基础上，将不包含i的i的倍数再放到前面时贡献值最大为多少。
            dp[j]=max(dp[j],dp[i]+(j-i)*cnt[j]);
        }
        MA=max(MA,dp[i]);//最后的dp[i]表示在i的基础上进行转移能得到的最大贡献，并去更新MA。
    }
    cout<<MA<<endl;

    return 0;
}

D2. Divan and Kostomuksha (hard version)

题意：将第一题$a[i]$的数据范围从$5 \times 10^6$变成了$2 \times 10^7$那么显然$O(nlogn)$的复杂度会超时，那我们还得进行优化操作。

分析：
我们的操作是将复杂度从$O(logn)->O(loglogn)$，我们会发现一个数如果拥有两个因子例如$8：2和4$那么我们第一步操作是$dp[2]->d[4]$，但是显然从$dp[4]$转移更优。所以我们只需要筛选出$1~N$的质因子就可以免去很多冗余的操作。同样$cnt[i]$的更新方向也从大到小更新，例如$dp[8]$这个数如果$dp[4]+1$那么$dp[2]$可以吃$dp[4]$的状态同样也会$+1$相当于$dp[8]$可以向下渗透，所以我们需要预处理的跑一便线性筛。

• 代码+注解：

#include <bits/stdc++.h>
using namespace std;
const int N = 20000010;
#define int long long 
int cnt[N], dp[N];
int prime[N], cntp;
bool st[N];
void get_prime(int n)
{
    for(int i=2;i<=n;i ++)
    {
        if(!st[i])prime[cntp++]=i;
        for(int j=0;i*prime[j]<=n;j++)
        {
            st[i*prime[j]]=true;
            if(i%prime[j]==0)break;
        }
    }
}
void solve ()
{
    get_prime(N - 1);//预处理线性筛
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        cnt[x]++;
    }
    for(int j=0;j<cntp;j++)
        for(int i=(N-1)/prime[j];i>=1;i--){
            cnt[i]+=cnt[i*prime[j]];
        }//向下渗透O(loglogn)
    dp[1]=cnt[1];
    int MA=0;
    for(int i=1;i<N;i++){
        for(int j=0;j<cntp&&i*prime[j]<N;j++){
            dp[i*prime[j]]=max(dp[i*prime[j]],cnt[i*prime[j]]*(i*prime[j]-i)+dp[i]);
        }
        MA=max(MA,dp[i]);
    }
    cout<<MA<<endl;
}
signed main ()
{
    solve();
    return 0;
}