CF1614D1 Divan and Kostomuksha (hard version) / CF1614D2 Divan and Kostomuksha (hard version) 题解

先考虑 D1 怎么做。容易想到记 $buc_i$ 表示 $a$ 序列中有多少个数是 $i$ 的倍数（可以写一个埃筛 $O(n\log n)$ 求出），然后记 $f_i$ 表示当前序列的 $\gcd$ 为 $i$，所有前缀的 $\gcd$ 的和最大是多少。看上去没有记录当前选择了多少个数不好处理，但是注意到处理 $f_i$ 的时候把所有 $i$ 的倍数加到序列里的贡献都是 $i$ 且不会对序列的 $\gcd$ 产生影响，而再往后加的话序列的 $\gcd$ 值一定会变小，加入 $i$ 对答案的贡献也同样会减小，因此计算 $f_i$ 的时候一定需要把所有 $i$ 的倍数全都加入到序列里。

因此可以想到初始条件为 $f_i=i\times buc_i$，转移方程为 $f_i\leftarrow f_{ij}+i(buc_i-buc_{ij})$（$buc_i-buc_{ij}$ 即为当前为 $i$ 的倍数且没有被加入到序列中的元素的数量）。转移的时候枚举 $i$ 的倍数可以做到 $O(V\log V)$，能够通过 D1。

此时注意到转移时一个决策 $i\leftarrow ij$ 可能成为不可被替代的最优解当且仅当 $j$ 是质数，因此考虑先筛出 $1\sim V$ 内所有的质数然后转移的时候只转移质数 $j$ 的 dp 值。而处理 $buc$ 数组时可以套用 Dirichlet 前缀和的技巧做到 $O(V\log\log V)$ 计算。因此总时间复杂度为 $O(V\log\log V)$，简单卡常即可通过 D2。