【codeforces757 Div2 D1】Divan and Kostomuksha(1614D1)题解

题目大意

$a_{1,2\ldots n}$ 可以任意改变顺序，最大化：

$$\gcd(a_1) + \gcd(a_1,a_2) + \ldots + \gcd(a_1,a_2,\ldots,a_n)$$

原题地址

思路

直接求 $\gcd$ 时间复杂度肯定会炸。所以我们用 $cnt[j]$ 表示因数包含 $j$ 的数的个数，用这样的计算方式代替求 $\gcd$。

借助 cnt 数组计算

这个前缀 $\gcd$ 大小会逐渐下降。假设最开始 $\gcd$ 为 $x$，那么对答案的贡献就是 $x \cdot cnt[x]$；然后假设 $\gcd$ 下降到了 $y$，那么可以推出 $y \mid x$（即 $x \bmod y = 0$），我们来计算这一部分数的贡献——因为实际上 $cnt[y]$ 包含了 $cnt[x]$，而 $cnt[x]$ 已经被计算过了，所以要减去它们，贡献为 $y \cdot (cnt[y] - cnt[x])$。

DP

上述分析并不能解出本题，但帮我们了解了递推关系。最优解法肯定与这种思路类似：把尽量大的，且与后面的数 gcd 大的数尽量放在前面。但是这么想是很难去推的，所以我们应该逆着来推：假设最开始前面的数的 $\gcd$ 就是 $1$，那么初始结果就是 $n$，然后我们不断地把 gcd 大的数放在前面，计算这么做增大的部分。

• 假设最开始所有数的 $\gcd$ 均为 $y$（实际上最开始我们是从 $1$ 开始的），那么初始结果就是 $cnt[y] \cdot y$。
• 然后我们把所有 $\gcd$ 为 $x$ 的数放在前面（$y \mid x$），那么增加的结果怎么计算呢？$cnt[x]$ 中的每个数在计算 $cnt[y]$ 的贡献时，已经被计算了一次，所以我们应该计算它们多出来的部分，即 $(x - y) \cdot cnt[x]$。
• 然后我们再把 $cnt[x]$ 中，$\gcd$ 为 $z$（$x \mid z$）的数放在前面，再次计算增加的数。

一直重复上述过程。

当然 $\gcd$ 可能会有很多个，我们并不能确定把哪个放在前面是最优的，所以此时我们就要用 DP 的做法了。那么我们改动一下上述推算结果，状态转移方程就能写出来了：

$$dp[j] = \max(dp[j],\ dp[i] + (j - i) \cdot cnt[j])$$

其中 $i \mid j$。

代码

#include <cstdio>
#include <iostream>
using namespace std;

const int maxN = 5e6;

int n;
long long dp[maxN + 10], cnt[maxN + 10];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        int x;
        scanf("%d", &x);
        cnt[x]++;
    }
    for(int i = 1; i <= maxN; ++i)
        for(int j = 2 * i; j <= maxN; j += i)
            cnt[i] += cnt[j];
    dp[1] = n;   
    long long ans = 0;     
    for(int i = 1; i <= maxN; ++i)
        for(int j = 2 * i; j <= maxN; j += i)
            dp[j] = max(dp[j], (j - i) * cnt[j] + dp[i]);
    for(int i = 1; i <= maxN; ++i)
        ans = max(ans, dp[i]);
    printf("%lld\n", ans);            
    return 0;
}