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

题目大意

给定$n$个正整数$a_{1,2...n}$。
可以任意改变顺序。
求$gcd(a_1)+gcd(a_1,a_2)+...+gcd(a_1,a_2,...,a_n)$的最大值。

原题地址

思路

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

借助$cnt$数组计算

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

DP

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

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

一直重复上述过程。

当然$gcd$可能会有很多个,我们并不能确定把哪个放在前面是最优的,所以此时我们就要用$DP$的做法了。
那么我们改动一下上述推算结果,状态转移方程就能写出来了
$dp[j]=max(dp[j],dp[i]+(j?i)?cnt[j])$,其中$i|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;
}