CF2112C
个人难度：黄 上位 / 绿 下位
标签：贪心，基础数学知识，DP
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目翻译：给定一个 NNN 个元素的数组 AAA。你可以进行以下操作若干次：
* 选择两个正整数 i,j(1≤i,j≤N)i,j(1\le i,j\le N)i,j(1≤i,j≤N)。
* 将 AiA_iAi 变成 gcd(Ai,Aj)\gcd(A_i,A_j)gcd(Ai ,Aj )，其中 gcd(x,y)\gcd(x,y)gcd(x,y) 表示 x,yx,yx,y 的最大公约数。
求把 AAA 数组的元素都相同的操作最小次数。1≤N≤5×1031\le N\le 5\times 10^31≤N≤5×103。
显然最后的数组 AAA 里面的元素为 AAA 所有元素的最大公约数。所以我们把题目变一下：
先把 AAA 里所有元素都除以一个 AAA 数组的所有最大公约数，然后就把问题转换成了把 AAA 数组元素全变成 111 的最小次数了。
手玩几个样例可以发现：
* 如果 AAA 数组存在为 111 的元素，则答案就为 AAA 中不为 111 的元素数量，因为每个不为 111 的元素只需要对 111 进行一次操作就行。
* 如果不存在，则求出把 AAA 数组中任意一个元素变为 111 的最小次数 XXX，然后再按上面的办法，操作次数为 X+N−1X+N-1X+N−1。
如何求出呢？
考虑分解质因子。显然 gcd(Ai,Aj)\gcd(A_i,A_j)gcd(Ai ,Aj ) 的结果的质因子集合为 AiA_iAi 的质因子集合与 AjA_jAj 的质因子集合的交集。
所以只要 AjA_jAj 没有 AiA_iAi 的某个质因子，gcd\gcdgcd 操作后 AiA_iAi 的这个质因子也会消失。
我们可以求出所有 AiA_iAi 有的而 AjA_jAj 没有的质因子集合，然后想办法凑出个和 AiA_iAi 质因子集合相同的集合（就是每个元素都得有）。
不难想到 DP。DP 代码也很好写，枚举每一个 AjA_jAj 选还是不选即可。
我们看看时间复杂度：
显然 500050005000 范围内，一个数顶多有 555 个质因子。所以质因子集合大小不超过 555。
所以总时间复杂度为 O(∑n2×2k)O(\sum n^2\times 2^k)O(∑n2×2k)，其中 k=5k=5k=5。
最大计算次数为 8×1088\times 10^88×108，会超时。
思考一下怎么优化。
优化 1
我们发现总共的状态总数也不超过 2k2^k2k 个，而重复的状态是无效的，只需保留一个即可。
所以我们可以用这种方法大大减小 DP 的状态数。
时间复杂度降低为 O(∑(n2×k+n×(2k)2))O(\sum (n^2\times k+n\times (2^k)^2))O(∑(n2×k+n×(2k)2))。
优化 2
注意到有 555 个不同质因子的只有 777 个数，有 444 个的只有 336336336 个数。
而且显然重复的 AiA_iAi 对降到 111 没有任何作用，所以我们去重一下，就可以把实际的 kkk 降到 333 左右了。
code：
测了一下，202ms。提交记录
