【题目大意】
给出一个$n$个数的序列${a_n}$，其中有些地方的数为0，要求你把这个序列填成一个1到$n$的排列，使得：
$(a_i, a_j) = 1$，当且仅当$(i, j) = 1$。多组数据。
$n leq 3 imes 10^5, Tleq 10$
CodeForces：无多组数据，$n leq 10^6$
【题解】
这题有点神奇啊。。
首先考虑序列全是0要怎么做。
考虑到如果两个数的位置含有的因数种类完全一样，那么它们是可以互换的。（这个挺显然的）
观察如果两个质数的出现次数相同，那么这两个质数的位置是可以互换的。
第一个结论的解释是：比如位置2，位置4，原来它们对应关系是2-2,4-4，那么变成2-4,4-2也仍然合法。（显然其他也成立）
第二个结论的解释是：比如2和3的出现次数相同，就是意思说$lfloor n/2 floor = lfloor n/3 floor$，那么可以把含有2的因数的所有数（比如1*2, 2*2, 3*2, ...）和含有3因数的所有数（1*3, 2*3, 3*3, ...）对应互换。这个显然是没有问题的。
那么全0的话，就分别计算两个结论的贡献即可。
如果有很多数可以互相互换，那么设这些数的数量为$n_i$，对答案的贡献就是$n_i !$
现在考虑如果有些点已经被填了数要怎么做。
下文说的因数个数，指质因数分解后，去掉重复因数后的序列。
考虑位置$x$填了数$y$，那么要满足$x$的因数个数要等于$y$的因数个数，因为本来$x$填的是$x$，现在填了$y$，那么如果有解的话，也要满足对于每个$(i, x) = 1$，$(a_i, y) = 1$。之前已经满足的是$(a_i, x) = 1$；反之也成立。所以当且仅当$x$和$y$的因数个数相同，才能满足这一点。
我们把$x$和$y$的因数按照大小排序，显然就是按照出现次数进行排序了（出现次数=$n/i$）。
那么我们要做的就是把$x$和$y$的每个因数进行匹配，那么就是排序后对应的位置进行匹配。显然这个匹配是一个一一对应关系（双射）。为什么这么做呢？相当于我钦定了这两个质数交换（实际上给了$a_i$已经钦定了）
如果有不能对应的，也就是第二个结论：出现次数不相等，那么显然无解。
在这里我还被能不能去掉之前的匹配，和其他重新匹配，类似于匈牙利这种想法卡了一会儿。。。。这个显然没有问题，因为我两边无论什么顺序都要匹配，不能调换使得不在匹配中。
然后如果对应关系出现了冲突，显然一个质数不能和两个同时互换，这情况也是无解。
对于填了数$a_i$，相当于我$a_i$这个位置被钦定改变了，也就是对于第一个结论，会少一部分数可以进行互换，需要扣除。
那么就写完了。
需要强调的是，处理1的问题，我们把1看做一个质数。这样处理起来比较方便。当然也可以特判之类的
把双射写成单射在CodeForces上有两种情况：①wa on 37；②AC。（分别对应两个单射）
CF数据太水了啊。。太垃圾了。
终于调完了
upd:原来的代码只能过单组数据，现在更新了。。
交CF请把N和F开到100w
# include <vector> # include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; const int N = 3e5 + 10, F = 3e5; const int mod = 1e9 + 7; int n, a[N], c[N], fac[N]; int p[F/3], pn, id[F]; bool isnp[F + 5]; inline void sieve() { isnp[0] = isnp[1] = 1; for (int i=2; i<=F; ++i) { if(!isnp[i]) p[++pn] = i, id[i] = pn; for (int j=1; j<=pn && i*p[j]<=F; ++j) { isnp[i*p[j]] = 1; if(i%p[j] == 0) break; } } } vector<int> y[N]; inline void divide() { y[1].push_back(1); for (int i=1; i<=pn; ++i) for (int j=p[i]; j<=F; j+=p[i]) y[j].push_back(p[i]); } inline void combine(int x) { c[x] = 1; for (int i=0; i<y[x].size(); ++i) c[x] = c[x] * y[x][i]; } int t[N], u[N], fr[N], rf[N]; inline void sol() { int ans = 1; cin >> n; for (int i=1; i<=n; ++i) scanf("%d", a+i); memset(t, 0, sizeof t); memset(u, 0, sizeof u); memset(rf, 0, sizeof rf); memset(fr, 0, sizeof fr); for (int i=1; i<=n; ++i) t[c[i]] ++; for (int i=1; i<=n; ++i) if(a[i] != 0) t[c[i]] --; for (int i=1; i<=n; ++i) ans = 1ll * ans * fac[t[i]] % mod; for (int i=1; i<=n; ++i) t[i] = 0; for (int i=1; i<=n; ++i) for (int j=0; j<y[i].size(); ++j) t[id[y[i][j]]] ++; for (int i=1; i<=n; ++i) { if(a[i] != 0) { if(y[i].size() != y[a[i]].size()) { puts("0"); return ; } for (int j=0; j<y[i].size(); ++j) { int ta = y[i][j], tb = y[a[i]][j]; ta = id[ta], tb = id[tb]; if(t[ta] != t[tb]) { puts("0"); return ; } if(fr[ta] && fr[ta] != tb) { puts("0"); return ; } fr[ta] = tb; if(rf[tb] && rf[tb] != ta) { puts("0"); return ; } rf[tb] = ta; } } } for (int i=1; i<=pn; ++i) if(!fr[i]) u[t[i]] ++; for (int i=1; i<=n; ++i) ans = 1ll * ans * fac[u[i]] % mod; cout << ans << endl; } int main() { freopen("perm.in", "r", stdin); freopen("perm.out", "w", stdout); int T; cin >> T; sieve(); fac[0] = 1; for (int i=1; i<=F; ++i) fac[i] = 1ll * fac[i-1] * i % mod; divide(); for (int i=1; i<=F; ++i) combine(i); isnp[1] = 0; p[++pn] = 1; id[1] = pn; while(T--) sol(); return 0; }