CF1986G2 Permutation Problem (Hard Version) 题解

Moya_Rao · 2025-06-20 16:52:02 · 题解

嘻嘻，来写一篇紫题题解。

首先，由于要求的是 i \times j \mid p_i \times p_j，所以考虑对每个 \dfrac{p_i}{i} 约分，变成 \dfrac{a_i}{b_i}。塞进 vector 里让它们一一对应起来。

约分以后 i,j 两个下标满足要求就当且仅当 b_i \mid a_j 并且 b_j \mid a_i 了。应该很显然吧。

枚举 b_i 的所有倍数尝试作为 a_j。尽管两个循环但是调和级数，这时间复杂度很显然是 O(n \log n) 的，而且可能还不到。

知道 a_j 就有待选 b_j 了，我们把这些 b_j 扔进一个桶里。

同样的，一开始我们知道 b_i，所以就有符合条件的 a_i。枚举这些 a_i 分别对应的因数 b_j，利用刚才桶里存的那些待选 b_j 的信息，累加答案。

然后就结束了。

最后输出的时候记得 \div 2，因为在我们的算法中 i < j 和 i > j 的情况都会被统计进去，可题目只需要 i < j 一种答案。