[CF1614D2] Divan and Kostomuksha (hard version)

令 $b_i=\gcd(a_1,a_2,\cdots,a_3)$， 不难发现 $b_{i+1}\mid b_i$。

于是我们设 $f_x$ 为将序列 $a$ 中所有 $x$ 的倍数重排得到序列 $t_1,t_2,\cdots,t_m$ 之后，$\sum_{i=1}^m\gcd(t_1,t_2,\cdots,t_i)$ 的最大值。

那么显然 $f$ 在 $x$ 处的值只会从它的所有倍数 $kx$ 处转移而来，并且 $f_{kx}$ 对应的最优的序列一定是 $f_x$ 对应的最优的序列的前缀。

转移方程为

$$\displaylines{f_x=\max_{kx\le\max\{a\}}\left\{f_{kx}+\sum_{i=1}^n[x\mid a_i\land kx\not\mid a_i]\right\} }$$

这样转移是 $O(n\log n)$ 的。

考虑到对于合数 $k=pq$（$p,q$ 不为 $1$），$f_{kx}\to f_{px}\to f_{qx}$ 的转移不比 $f_{kx}\to f_{x}$ 劣，所以实际上可以仅枚举所有质数 $k$ 进行转移。