题解：CF698F Coprime Permutation

· · 题解

考虑对数做等价类划分。不难发现互质的限制只与哪些质因子出现相关，因此这样的同种数在内部可以任意轮换。

但是上面不是必要条件。例如 n=5 时 3,5 可以交换。记 P 为质数集合。更一般的，容易发现 \{1\}\cup(P\cap (\dfrac{n}{2},n]) 可以轮换，P\cap (\dfrac{n}{3},\dfrac{n}{2}] 可以轮换，以此类推。所以对于质数来说，根据 \lfloor\dfrac{n}{p}\rfloor 可以划分为等价类（特殊考虑 1）。而且在钦定质数所填位置的情况下，每个位置的「出现质因子集合」是固定的。

考虑推广到计数。每种「出现质因子集合」对应个数为 c，答案就要乘 c!。而对于质数的等价类，若大小为 c，同理乘上 c!。

只需要判一下无解即可。

https://codeforces.com/contest/698/submission/3484209790。