GCD + DP + 调和级数/埃式筛
[Problem - D - Codeforces](https://codeforces.com/contest/1610/problem/D)
题意
给出一个长度为 \(n\;(1<=n<=10^5)\) 的数组 \(a[i]\;(1<=a[i]<=2*10^7)\)
可以重新排列 \(a\) 数组，使得 \(\sum\limits_{i=1}^n\gcd(a_1,a_2,...,a_i)\) 最大
思路
-
设 \(cnt[x]\) 为 \(x\) 的倍数有多少个，easy版本可用调和级数，hard版本可 \(n*\sqrt{a[i]}\) 分解因数
-
若 \(x\) 开头，最优策略是把 \(x\) 的倍数全都紧接着放在 \(x\) 之后，他们的贡献为 \(cnt[x]*x\)
-
设以 \(x\) 作为 \(gcd(a[1])\) 的答案为 \(f[x]\)（这里并非 \(a[1]\) 开头 \(gcd(a[1])\) 就是 \(a[1]\), \(a[1]\) 的任何因数都可以）, 把 \(x\) 的倍数 \(y\) 放到 \(x\) 的前面时会更优，因此 \(f[x]->f[y]\) 转移
-
在 \(f[x]\) 向 \(f[y]\) 转移的过程中，除了 \(x\) 的倍数 \(cnt[x]\) 个以外的 \(n-cnt[x]\) 个数对贡献并没有改变
且是 \(x\) 的倍数但不是 \(y\) 的倍数的数的贡献也没有改变，只有 \(cnt[y]\) 个数的贡献由 \(x\) 变成了 \(y\), 因此转移方程为
\(f[y]=max(f[y],f[x]+(y-x)*cnt[y])\)
-
easy 版本可用调和级数；hard版本考虑优化，其实并非 \(x\) 向它的每个倍数 \(y\) 都需要转移，只需要转移向素数倍的 \(y\) 就行（感受一下，应该也可以证）
类比埃式筛，时间复杂度为 \(O(nloglogn)\)
代码
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
typedef pair<int, int> PII;
const int N = 2e7 + 10;
ll f[N];
int n;
ll cnt[N];
int pr[N / 5], p[N];
int t;
void get_primes(int n)
{
p[1] = 1;
for (int i = 2; i <= n; i++)
{
if (!p[i])
{
p[i] = i;
pr[++t] = i;
}
for (int j = 1; j <= t && pr[j] <= n / i; j++)
{
p[i * pr[j]] = pr[j];
if (p[i] == pr[j])
break;
}
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
get_primes(N - 10);
cin >> n;
for (int i = 1, x; i <= n; i++)
{
cin >> x;
for (int j = 1; j <= x / j; j++)
{
if (x % j == 0)
{
cnt[j]++;
if (j != x / j)
cnt[x / j]++;
}
}
}
f[1] = n;
for (int x = 1; x <= N - 10; x++)
{
for (int i = 1; i <= t && pr[i] <= (N - 10) / x; i++)
{
int y = x * pr[i];
f[y] = max(f[y], f[x] + (y - x) * cnt[y]);
}
}
cout << *max_element(f + 1, f + N - 9) << endl;
return 0;
}