D1. Divan and Kostomuksha (easy version)

记$d{p}_{i}dp\_i$表示把$\gcd \{\backslash gcd\}$为$i\{i\}$的一组数放到前面的贡献，$cn{t}_i\{cnt\_i\}$表示含有因子$i\{i\}$的数的个数。

状态转移方程有：$d{p}_i=max(d{p}_i,d{p}_d+cn{t}_i\ast (i-d)),[d\mathrm{\mid }i]\{dp\_i=max(dp\_i,dp\_d+cnt\_i*(i-d))\},[d|i]$，可以直接用调和级数转移$O(N\log N)\{O(N\backslash log\; N)\}$

求$cn{t}_i\{cnt\_i\}$可以直接用调和级数$O(N\log N)\{O(N\backslash log\; N)\}$

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=5e6+7,mod=1e9+7;
ll f[maxn],res;
int cnt[maxn];
int main() {
	cin.sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1,x;i<=n;++i) {
		cin>>x;
		++cnt[x];
	}
	for(int i=1;i<=5e6;++i) {
		for(int j=i+i;j<=5e6;j+=i) cnt[i]+=cnt[j];
	}
	f[1]=n;
	for(int i=1;i<=5e6;++i) {
		res=max(res,f[i]);
		for(int j=i+i;j<=5e6;j+=i) f[j]=max(f[j],f[i]+1LL*cnt[j]*(j-i));
	}
	cout<<res<<'\n';
	return 0;
}

D2. Divan and Kostomuksha (hard version)

直接交$D1\{D1\}$代码会T,（主要是状态转移的那个$O(N\log N)\{O(N\backslash log\; N)\}$里的$d{p}_i\{dp\_i\}$开的是$longlong\{long\backslash \; long\}$，有常数）。

可以用类似线性筛的写法$O(N)\{O(N)\}$求$cn{t}_i\{cnt\_i\}$.

for(int p:prime) {
	for(int i=M/p;i;--i) cnt[i]+=cnt[i*p];
}

$x=p_1\ast p_2\ast p_3,y=p_3\{x=p\_1*p\_2*p\_3,y=p\_3\}$，$cn{t}_y\{cnt\_y\}$累加$cn{t}_x\{cnt\_x\}$的过程：

$cn{t}_{p_2\ast p_3}+=cn{t}_x\{cnt\_\{p\_2*p\_3\}+=cnt\_x\}$

$cn{t}_{p_3}+=cn{t}_{p_1\ast p_3}\{cnt\_\{p\_3\}+=cnt\_\{p\_1*p\_3\}\}$

$cn{t}_{p_1\ast p_3}+=cn{t}_x\{cnt\_\{p\_1*p\_3\}+=cnt\_x\}$

$cn{t}_{p_3}+=cn{t}_{p_2\ast p_3}\{cnt\_\{p\_3\}+=cnt\_\{p\_2*p\_3\}\}$

保证不会漏算或者多算（优化不大）。

对于状态转移来说，每次只转移质数倍是最优的。即$d{p}_1->d{p}_{p_1}->d{p}_{p_1\ast p_2}\{dp\_1->dp\_\{p\_1\}->dp\_\{p\_1*p\_2\}\}$优于$d{p}_1->d{p}_{p_1\ast p_2}\{dp\_1->dp\_\{p\_1*p\_2\}\}$：

$d{p}_1+(cn{t}_{p_1}-cn{t}_{p_1\ast p_2})\ast (p_1-1)+cn{t}_{p_1\ast p_2}\ast (p_1\ast p_2-1)>=d{p}_1+cn{t}_{p_1\ast p_2}\ast (p_1\ast p_2-1)\{dp\_1+(cnt\_\{p\_1\}-cnt\_\{p\_1*p\_2\})*(p\_1-1)+cnt\_\{p\_1*p\_2\}*(p\_1*p\_2-1)>=dp\_1+cnt\_\{p\_1*p\_2\}*(p\_1*p\_2-1)\}$

所以可以枚举素数转移，素数的数量$\log N\{\backslash log\; N\}$，复杂度好像是$O(N\log \log N)\{O(N\backslash log\; \backslash log\; N)\}$

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=2e7+7,M=2e7,mod=1e9+7;
vector<int>prime;
bool vis[maxn];
inline void init() {
	for(int i=2; i<maxn; ++i) {
		if(!vis[i]) prime.emplace_back(i);
		for(auto j:prime) {
			if(i*j>=maxn) break;
			vis[i*j]=1;
			if(i%j==0) break;
		}
	}
}
ll f[maxn],res;
int cnt[maxn];
int main() {
	init();
	cin.sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1,x;i<=n;++i) {
		cin>>x;
		++cnt[x];
	}
	for(int p:prime) {
		for(int i=M/p;i;--i) cnt[i]+=cnt[i*p];
	}
	f[1]=n;
	for(int i=1;i<=M;++i) {
		res=max(res,f[i]);
		for(int p:prime) {
			if(i*p>M) break;
			f[i*p]=max(f[i*p],f[i]+1LL*cnt[i*p]*i*(p-1));
		}
	}
	cout<<res<<'\n';
	return 0;
}