题目简述：给定$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 \not| 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$种可能），
CodeForces 1103D. Professional layer
原文：https://www.cnblogs.com/TinyWong/p/10350159.html