定义质数 $i$ 的数链（集合）$S_{i}$ 包含了 $i$ 在 $[1,n]$ 中所有倍数。
那么对于 $p$ 来说，将 $i$ 的 $S_i$ 当作下标集合，满足 $\gcd(p_a,p_b),{a,b}\subseteq S_i$ 。假设这些 $p_a,p_b$ 均为质数 $t$ 的倍数，那么相当于 $S_i$ 作下标集合时，在 $p$ 中对应的是 $S_t$，称用 $i$ 替换了 $t$，容易发现 $i$ 能替换 $t$ 的充要条件为 $|S_i|=|S_t|$ 。
将每个质数 $i$ 以 $|S_i|$ 为关键字分组，对于关键字等于 $k$ 的所有的 $s_k$ 个 $i$ 都可以互相替换，方案数显然为 $s_k!$ 。
同时注意到，如果两个位置 $i,j$ 的数链覆盖集合（由包含 $i/j$ 的数链的下标构成的集合）一样，那么这两个位置是等价的，可以交换，计算方式于上面相仿。
接下来考虑怎么处理原有 $p_i$ 。
首先 $p_i$ 的数链覆盖集合一定能找到一种替换方案，以上面的替换方法替换为 $i$ 的数链覆盖集合。如果找不到，那么答案为 $0$ 。
直接处理这个问题不好办，不过可以发现：对于 $a,b<\sqrt{n}$ 的质数 $a,b$，一定有 $|S_a|\not=|S_b|$（因为 $|S_a|,|S_b|\geq \sqrt{n}>a,b$，显然不可能有 $|S_a|=|S_b|$），也就是说 $a,b$ 必然不存在替换关系。
同时因为 $p_i,i$ 都至多存在一个不小于 $\sqrt{n}$ 的质因子，只需要处理这种质因子的替换关系即可。（对于小于 $\sqrt{n}$ 的质因子只能相等，否则非法）。
对每个质因子记录 in, out 表示强制被谁替换，又强制替换谁，因为强制被替换和替换谁都是面向一个对象，如果存在多于一个对象则非法。
模拟一遍即可，注意特殊处理 $1$ 的情况（可以发 $1$ 和出现次数为 $1$ 的大质数其实等价）。
0 条评论