题目简述：给定$1 leq n leq 10^6$个正整数$1 leq a_i leq 10^{12}$，修改第$i$个正整数$a_i$的花费为$1 leq e_i leq 10^9$，以及正整数$1 leq k leq 10^{12}$。要求选出若干个正整数进行一次修改，使得修改后所有正整数的最大公约数等于$1$。修改操作为：对于正整数$a$，选择$a$的一个约数$d leq k$，把$a$修改为$a/d$。设选出并修改的正整数有$x$个，他们的花费之和为$y$，则总的修改花费为$xy$。求最小花费。
解：code
设$d = gcd (a_1, a_2, dots, a_n) = p_1^{s_1} p_2^{s_2} dots p_m^{s_m}$，其中$p_i$为互不相同的质数且$s_i geq 1$。由$d leq 10^{12}$，可知$m leq 11$。
观察1：若$a_i$存在不同于$p_1, p_2, dots, p_m$的质因数$p$，则将$a_i$替换为$a_i/p$不会影响最小花费。
故可假设$a_i = p_1^{s_{i1}} p_2^{s_{i2}} dots p_m^{s_{im}}$，我们称满足这一条件的$a_i$为“正规化”的。
观察2：正规化的$a_i$序列中，不同元素个数$M leq 11598$。这个上界当$d = 2 cdot 3 cdot 5 cdot 7 cdot 11 cdot 13$时取到。
我们修改$a_i$的目标是，对任意$1 leq j leq m$，都存在一个$a_i$，使得$p_j ot| a_i$。为了最小花费，显然对任一$d$的质因数$p_j$，我们只需要选择恰好一个$a_i$，将其修改为不被$p_j$整除即可。因此：
观察3：我们最多只需要修改$m$个$a_i$。
从而真正有用的（即可能被修改的）$a_i$只能是：每种正规化$a_i$中，$e_i$值最小的$m$个。总共$m M$个。
对$mM$个真正有用的每个元素$(a_i, e_i)$， 枚举从$a_i$中除去的质因数的所有可能组合（一共需要检验$2^m-1$种可能）。若$a_i$可以除去质因数组合$s$，则记为$s models a_i$。
我们把$(a_i, e_i)$按照$e_i$从小到大排序。令$F[i][x][s]$表示前$i$个元素中修改$x$个元素，且$s$描述了所除去的质因数的情况下的最小花费。则
$$ F[i][x][s] = min_{t subseteq s, t models a_i} { F[i-1][x][s], F[i-1][x-1][s-t]+e_i }. $$
动态规划有用状态数为$mM2^m$。
真正有用的元素及其除去的质因数组合并非$mM2^m$种，而是$m 2^m$种，因为对于每一种除去的质因数组合，我们同样也只会关心$e_i$值最小的$m$个。故在动态规划状态转移时，只需要考虑有用的元素及其质因数组合，假设$s$是【有用的$(a_i, e_i)$】的有用质因数组合，我们只需考虑以下动态规划转移：
$$ F[i+1][x+1][s cup t] gets min { F[i+1][x+1][s cup t], F[i][x][t]+e_i }, $$
其中$t cap s = emptyset$。即，$t$枚举$s$的补的子集。（枚举子集方式可参见这里。）此种转移数至多为$m^2 3^m$。
综上，时间复杂度为$O(n log n+m M 2^m+m^2 3^m)$。