题解：CF2115A Gellyfish and Flaming Peony
AIerqwq
·
·
题解
题目翻译：给定一个 N 个元素的数组 A。你可以进行以下操作若干次：
- 选择两个正整数 i,j(1\le i,j\le N)。
- 将 A_i 变成 \gcd(A_i,A_j)，其中 \gcd(x,y) 表示 x,y 的最大公约数。
求把 A 数组的元素都相同的操作最小次数。1\le N,A_i\le 5\times 10^3。
显然最后的数组 A 里面的元素为 A 所有元素的最大公约数。所以我们把题目变一下：
先把 A 里所有元素都除以一个 A 数组的所有最大公约数，然后就把问题转换成了把 A 数组元素全变成 1 的最小次数了。
手玩几个样例可以发现：
- 如果 A 数组存在为 1 的元素，则答案就为 A 中不为 1 的元素数量，因为每个不为 1 的元素只需要对 1 进行一次操作就行。
- 如果不存在，则求出把 A 数组中任意一个元素变为 1 的最小次数 X，然后再按上面的办法，操作次数为 X+N-1。
如何求出呢？
考虑分解质因子。显然 \gcd(A_i,A_j) 的结果的质因子集合为 A_i 的质因子集合与 A_j 的质因子集合的交集。
所以只要 A_j 没有 A_i 的某个质因子，\gcd 操作后 A_i 的这个质因子也会消失。
我们可以求出所有 A_i 有的而 A_j 没有的质因子集合，然后想办法凑出个和 A_i 质因子集合相同的集合（就是每个元素都得有）。
不难想到 DP。DP 代码也很好写，枚举每一个 A_j 选还是不选即可。
代码。
我们看看时间复杂度：
显然 5000 范围内，一个数顶多有 5 个质因子。所以质因子集合大小不超过 5。
所以总时间复杂度为 O(\sum n^2\times 2^k)，其中 k=5。
最大计算次数为 8\times 10^8，会超时。
思考一下怎么优化。
优化 1
我们发现总共的状态总数也不超过 2^k 个，而重复的状态是无效的，只需保留一个即可。
所以我们可以用这种方法大大减小 DP 的状态数。
时间复杂度降低为 O(\sum (n^2\times k+n\times (2^k)^2))。
优化 2
注意到有 5 个不同质因子的只有 7 个数，有 4 个的只有 336 个数。
而且显然重复的 A_i 对降到 1 没有任何作用，所以我们去重一下，就可以把实际的 k 降到 3 左右了。
代码在这。
测了一下，202ms。提交记录