定义质数 $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$ 的大质数其实等价)。

代码:Submission #127662008 – Codeforces

分类: 文章

Qiuly

QAQ

0 条评论

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

*

code