题解

思路

对一个可能成为前缀最大公约数的整数 $d$，统计数组中有多少元素是 $d$ 的倍数。最优排列可以看成沿“当前最大公约数”不断下降；从 $d$ 进入更大的倍数状态时，应先放置仍属于该倍数的元素。

做法

令 $c_d$ 为数组中能被 $d$ 整除的元素个数，令 $f_d$ 表示只考虑这些元素、最终前缀最大公约数降到 $d$ 时的最大贡献。

不继续细分时，贡献为 $d\cdot c_d$。若先处理能被 $dp$ 整除的元素，其中 $p$ 是质数，则这部分得到 $f_{dp}$，剩余 $c_d-c_{dp}$ 个元素各贡献 $d$：

$$f_d=\max\left(d c_d,\max_{p\text{ 为质数},\,dp\le A}\left(f_{dp}+d(c_d-c_{dp})\right)\right).$$

只需考虑质数倍数：任何合数倍数都可沿质因子逐步到达。按 $d$ 递减计算，答案为 $f_1$。$c_d$ 通过枚举 $d$ 的所有倍数求得。

子任务一枚举全部排列并计算前缀最大公约数和。子任务二满足最大值不超过 5000，可在计算倍数计数后，对每个 d 枚举所有更大的倍数 m 做完整转移；满分做法只枚举质数倍状态。

复杂度

设 $A=\max a_i$。计数总复杂度为 $O(A\log A)$，中档完整倍数转移为 $O(A\log A)$，满分质数转移为 $O(A\log\log A)$；空间复杂度为 $O(A)$。