西电校赛遇到的神秘题目。
题目
称长度为 $n$ 的排列 $p$ 是完美的，当且仅当对于任意 $1 \leq i < j \leq n$，$p_i \perp p_j$ 当且仅当 $i \perp j$（这里的垂直符号代表互素）。
给定正整数 $n$ 满足 $n \leq 10^6$，请求出长度为 $n$ 的完美的排列的总数，对 $10^9+7$ 取模。
初步思考
注意到恒等排列 $p_i \equiv i$ 一定合法。
考虑用交换构造出所有排列。什么交换是不合法的呢？
对于两个位置 $i, j$，如果有另一个位置 $k$ 与 $i$ 不互素而与 $j$ 互素，或反之（即 $k$ 与 $i$ 和 $j$ 的互素性不同），则称 $k$ 是能区分 $i$ 和 $j$ 的一个证人。
如果 $i$ 和 $j$ 有证人，则我们不能随意交换它们，否则与那个证人之间的互素关系就会发生变化。
反之，我们可以任意交换放在这两个位置上的数。
我们称两个位置没有证人为“同类”。注意到这个关系具备传递性，从而是等价关系。
那么这些位置上能放的数字就是相同的集合，可以任意排列。
刻画同类关系。注意到两个数是同类，当且仅当它们的质因子集合是相同的。
于是不难想到用无平方因子数作为一类数的代表元。线性筛预处理每个位置的代表元。
预处理阶乘。
发现有另一类可能的变换：对于大于 $n/2$ 的素数，能区分它们和其他数的证人太大，所以这些数以及 1 之间是同类的。
实现以上所有的逻辑。
然后，我们惊喜的发现代码能够通过 $n=20$，却在 $n=500$ 时莫名其妙的 WA 了。
完整结论
考虑两个素数 $p, q$ 满足 $\lfloor n/p \rfloor = \lfloor n/q \rfloor$。
我们可以完整地交换它们的所有倍数。换言之，对于 $a = k_1 p$ 和 $b = k_2 q$，我们可以令 $p_a = k_1 q$，$p_b = k_2 p$，得到的排列仍然合法（是“完美的”）。
实现这个逻辑。然后就对了。
正解思路
上面的补丁看上去毫无逻辑，完全不能理解为什么这是对的。同时，我们也不能理解为什么没有其他的自由度。
在最初的思路上继续尝试是没有前途的。正解有完全不同的另一种视角。
考虑互素图。这是一个有 $n$ 个节点，标号为 $1, 2, 3, \cdots n$ 的无向图。对于两个节点 $i, j$，它们之间有边当且仅当 $i \perp j$。
以及它的补图非互素图：对于两个节点 $i, j$，它们之间有边当且仅当 $i \not \perp j。$
我们的任务本质上是对这个图进行图自同构计数。
解释一下概念：两个图 $G_1, G_2$ 的一个同构 $f$ 是一个从 $G_1$ 的点集到 $G_2$ 的点集的双射，满足 $\forall u, v \in G_1, (f(u), f(v)) \in G_2 \Leftrightarrow (u, v) \in G_1$，即映射后的点之间有边等价于原来的点之间有边。
自同构就是 $G_1=G_2$ 时的图同构。
接下来，我们将运用一个重要的性质：图同构保持点邻域的包含关系。
我们定义一个点的邻域 $N(u)$ 是这个点本身，以及所有与之有边相连的点所构成的集合：
$$ N(u) = \{ u \} \cup \{v \mid (u, v) \in G \} $$我们需要证明的是：对于 $G_1$ 与 $G_2$ 的图同构 $f$，$\forall u, v \in G_1, N(u) \subseteq N(v) \Leftrightarrow N(f(u)) \subseteq N(f(v))$。
证明的方法是考虑定义。首先我们有 $N(f(u)) = f(N(u))$，因为对于每个和 $u$ 有边相连的点，同构之后的点根据定义也必然和 $u$ 同构之后的点有边。而对于和 $u$ 没有边相连的点，根据定义，同样在同构之后也不会和 $f(u)$ 有边。
于是，我们相当于要证明 $f(N(u)) \subseteq f(N(v))$。这是显然的，因为对于一个元素 $x \in N(v)$，$f(N(v))$ 中一定把原来在 $N(v)$ 中的 $x$ 变成了 $f(x)$，这是由“映射作用于集合”的定义决定的。
有了这个引理之后，我们就知道了一点：我们一定不能把素数和合数相互映射。因为素数不包含任何其他点的邻域，而合数包含其他点的邻域，这样的交换会破坏掉邻域的包含关系，必定不合法。
于是我们应当分别考虑素数与合数之间各自的置换关系。
在素数中，我们考虑一个简单的限制：每个点 $u$ 的对应点 $f(u)$ 的邻域大小（即度数加一）必定和 $N(u)$ 的大小一样。
做完这个限制之后，素数之间就可以任意置换了吗？
暂时搁置疑问。假设确定了素数的置换，我们考虑合数的置换。
运用邻域包含引理。对一个合数 $x$，$f(x)$ 的每一个质因子 $p$ 都一定有一个 $x$ 的质因子 $q$ 与之对应，满足 $f(q)=p$，反过来也成立。即，$f$ 是 $x$ 与 $f(x)$ 的质因子集合间的一一对应。
这是容易理解的。
对于相同的质因子集合，考虑我们最初的想法。不难发现它们之间可以任意互相交换。所以，确定了素数的置换之后，我们一定会有一堆合法的合数置换，满足我们最初的想法。
这一步有点类似上下界的思想：我们先找出了一个必要条件，之后发现这是充分的。
但这一步其实有个漏洞：
不难发现它们之间可以任意互相交换
这不完全正确。理由如下：
虽然对素数的置换满足了必要条件，但由此衍生的对合数的等价类（质因子集合的等价类）的置换并没有自动满足度数相等的必要条件。
我们需要解决这个问题。
下面的证明中，我们将采取这样的路径：
如果等价类 1 在经过素数的置换之后被对应到等价类 2，那么一个属于等价类 1 的数，变换之后一定对应到一个等价类 2 的数，而不会由于变得比 $n$ 更大或其他原因而不合法。
如果我们能证明上面的结论，我们就可以证明所有等价类之间的置换都满足等价类大小相等的条件。原因如下：
考虑等价类置换中的每个轮换。能把等价类 1 对应到等价类 2，说明这是一个单射，而 2 的大小不小于 1 的大小。以此类推，最后有 $a \le b \le c \le ... \le a$ 类似的式子，就证明整个轮换里所有等价类都一样大。
于是证明变得简单了：
首先考虑这种变换是否保持我们期望的质因子集合的性质，具体的，质因子集合间的包含关系。
这相对容易。考虑两个数的质因子集合 $a\subseteq b$。在变换之后，我们考察 $a$ 中的每个元素 $x$。如果 $x$ 变成了 $y$（我们构造的置换中 $f(x)=y$），$b$ 中的 $x$ 也就变成了 $y$，$f(x)$ 仍然属于 $f(b)$。
类似的，也容易证明如果 $a \not \subseteq b$，变换后 $f(a) \not \subseteq f(b)$ 成立。
然后我们需要证明，变换不会使数变得过大。
对于所有只含有不超过一个 $p$ 或 $q$ 的东西，把其中的 $p$ 改为 $q$ 之后，这个数仍然不超过 $n$。
这是显然的，因为 $\lfloor n/p \rfloor = \lfloor n/q \rfloor$。如果 $kp \leq n$，那么 $kq$ 自然也不超过 $n$。
所以，真正的问题是，对于那些含有超过一个 $p$ 或 $q$ 的数呢？
答案是，这类数根本不存在。
$d := \lfloor n/p \rfloor = \lfloor n/q \rfloor$ 意味着 $d \leq n/p < n/q < d + 1$（这里假设 $p>q$）。
于是，$n/q - n/p < 1$，$\frac{n(p-q)}{pq} < 1$。
$pq > n(p - q) \geq n$
这说明 $p, q$ 中至少有一个大于 $\sqrt n$（因为必须有 $p \neq q$）。而另一个显然也不可能小于 $\sqrt n$，所以任意数都不可能包含超过一个 $p$ 或 $q$ 的因子。
我们将证明：$q \geq \sqrt n$。
设 $I = \lfloor \sqrt n \rfloor$。
我们有 $\lfloor n/p \rfloor \leq I$ 和 $\lfloor n/q \rfloor \geq \lfloor n/I \rfloor$
显然，只有在 $\lfloor n/I \rfloor = I$ 且两边同时取等时，才有可能成立。
看左边：$\lfloor n/p \rfloor = I$ 这意味着 $n/p \geq I, p \leq n/I$。
右边：$\lfloor n/q \rfloor = I$ 意味着 $n/q < I + 1, I > q > n/(I+1)$，进一步推出 $I(I+1)>n$。
这也就推出，$\lfloor n/I \rfloor \leq n/I < I+1$。外加上 $I \leq \sqrt n < p \leq n/I < I+1$，$p$ 是一个整数，却被夹在两个相邻的整数之间，这显然是不可能的。
于是，矛盾。我们得出：$q > \sqrt n$。
如果直接这么写，会当场倒闭，连样例都过不去。我们的推理中哪里缺失了呢？
我们分类讨论了质数与合数，但唯独没有讨论 1。
其实，1 在这里的地位和素数是类似的：它的邻域不包含其他任何数的邻域。
所以自然遵循和素数同样的规则：可以与任意度数相同的素数互相交换。注意到 1 与任何数都互素，所以它在非互素图中的度数是 0，也就只能和那些度数为 0，即大于 $n/2$ 的素数相互交换了。
至此，这个题就做完了。