记$P$为$[1,n]$中所有素数构成的集合，$g(n)$为$n$所有素因子乘积（特别的，$g(1)=1$）
对于一个合法排列${q_{i}}$，注意到$forall xin Pcup{1},q_{x}$两两互素，也即每一个素因子至多只能在其中出现一次，分析数量不难得到每一个数至多只能包含一个素因子（注意仅有1不包含素因子）
换言之，$forall xin Pcup {1},g(q_{x})$恰为$Pcup {1}$的一个排列
不妨假设已经确定这些$g(q_{x})$，那么有$g(q_{i})=prod_{xin Pcup{1},gcd(x,i) e 1}g(q_{x})$（其中$i e 1$，注意到包含$g(q_{x})$这个素因子当且仅当$gcd(x,i) e 1$，同时这样考虑了$P$中所有素数，即正确）
进一步的，对于$g(x)=g(y)$的$x$和$y$在是否互素的判定中是等价的，因此此时已经可以确定${q_{i}}$合法，并且仅需保证数量相同（即$forall x,sum_{g(i)=x}1=sum_{g(q_{i})=x}1$），其内部是可以任意排列的
此时，问题即变为怎样的$Pcup {1}$的排列（填入$forall xin Pcup{1},g(q_{x})$）能保证"数量相同"
（下面较详细地分析了细节，如果感性理解可以直接跳过看结论）
对"数量相同"的式子容斥，前者即为
$$
sum_{g(i)=x}1=egin{cases}0&mu(x)=0\sum_{S_{0}subseteq Ssubseteq P}(-1)^{|S|-|S_{0}|}sum_{(prod_{pin S}p)mid g(i)}1&mu(x) e 0end{cases}
$$
（$S_{0}$为$x$素因子集合，另外注意$mu(prod_{pin S}p) e 0$）类似地，后者$sum_{g(q_{i})=x}1$只需要将式子中的$g(i)$均改为$g(q_{i})$即可
由此，"数量相同"的充分条件即$forall mu(x) e 0,sum_{xmid g(i)}1=sum_{xmid g(q_{i})}1$，同时显然这也是必要的
关于前者，由于$mu(x) e 0$，那么$xmid g(i)$即等价于$xmid i$，前者也即为$lfloorfrac{n}{x} floor$
关于后者，再令$S_{0}={pmid pin Pcup{1}$且$q_{p} e 1,g(q_{p})mid x}$，那么$xmid g(q_{i})$（其中$i e 1$）根据$g(q_{i})$的式子即等价于$forall pin S_{0},gcd(p,i) e 1$，又因为$pin S_{0}subseteq Pcup {1},gcd(p,i) e 1$也即$p e 1$且$pmid i$
换言之，后者也即为$egin{cases}n&(x=1)\ [xmid g(q_{1})]+egin{cases}0&q_{1} e 1,g(q_{1})mid x\lfloorfrac{n}{prod_{pin S_{0}}p} floor&otherwiseend{cases}&(x e 1)end{cases}$
对这三类分别讨论（注意需要同时满足），具体如下——
1.$x=1$时必然成立（与$g(q_{x})$无关）
2.$x e 1$且$q_{1} e 1,g(q_{1})mid x$时，取$x=g(q_{1})$即有$lfloorfrac{n}{g(q_{1})} floor=1$，推出$g(q_{1})>lfloorfrac{n}{2} floor$，同时此时$q_{1}$必然恰为$g(q_{1})$（而不能是$g(q_{1})^{alpha}$），同时此时$x$必然为$g(q_{1})$，也即成立（另外注意$q_{1}$还可以等于1）
3.$x e 1$且$otherwise$，取$x$为$ e q_{1}$的素数，令$p$满足$pin Pcup{1}$且$g(q_{p})=x$，即有$lfloorfrac{n}{x} floor=lfloorfrac{n}{p} floor$，并且$xle sqrt{n}$时此式成立必然要有$p=x$，证明如下：
若$xp>n$，则$lfloorfrac{n}{p} floor<xle sqrt{n}le lfloorfrac{n}{x} floor$，即不相等
若$xple n$，不妨假设$x<p$，则$lfloorfrac{n}{x} floor=p+lfloorfrac{n-xp}{x} floor>x+lfloorfrac{n-xp}{p} floor$
而在此条件下，考虑$x$即是要求$lfloorfrac{n}{x} floor=lfloorfrac{n}{prod_{pin S_{0}}p} floor$，此时将$x$的素因子和$p$对应，其中仅有$>sqrt{n}$的项不相同，这至多存在一项且被$n$除后也相同，再除以相同的数显然仍相同
综上，"数量相同"当且仅当满足以下条件：
1.$q_{1}=1$或$q_{1}in P$且$q_{1}>lfloorfrac{n}{2} floor$
2.$forall xin Pcup{1}$且$x e q_{1}$，有$lfloorfrac{n}{x} floor=lfloorfrac{n}{p} floor$（其中$pin Pcup{1}$且$g(q_{p})=x$）
这样填完这个排列后，若$q_{1}=1$即已经填完，$q_{1} e 1$即还剩下一个位置，该位置（下标）为$>lfloorfrac{n}{2} floor$的素数，并且即要填剩下的1，因此实际上即将$lfloorfrac{n}{1} floor$看作1就可以归为一种情况
令$h(x)=egin{cases}1&(x=1)\lfloorfrac{n}{x} floor&(xin P)end{cases}$，那么"数量相同"当且仅当$forall xin Pcup{1},h(x)=h(g(q_{x}))$，换言之可以看作$h(x)$相同的数内部可以任意排列
接下来，考虑若干个给定的$q_{i}$，处理过程如下——
1.$i$和$q_{i}$不超过$sqrt{n}$的素因子（存在性）应该相同，且必须都存在/不存在$>sqrt{n}$的素因子（显然至多一个）
2.（若$i$和$q_{i}$都存在$>sqrt{n}$的素因子）令$p_{1},p_{2}$分别为$i$和$q_{i}$大于$sqrt{n}$的素因子，则需要满足$lfloorfrac{n}{p_{1}} floor=lfloorfrac{n}{p_{2}} floor$，并且在$xin Pcup{1}$的排列中强制$g(q_{p_{1}})=p_{2}$，记录这样的关系（防止重复）并将$h(p_{2})$所在组去掉一个
（$le sqrt{n}$的素因子不需要减小，因为其本身必须对应相同）
3.对于最后$g(q_{i})$确定后的排列中，$g(q_{i})$所在的组减少一个数
最终，将两者排列（求阶乘）相乘即可
时间复杂度为$o(n)$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 1000005 4 #define mod 1000000007 5 #define ll long long 6 int n,ans,a[N],fac[N],vis[N],p[N],mx[N],Mn[N],f[N],r0[N],r1[N],cnt[N],cnt0[N]; 7 int main(){ 8 fac[0]=mx[1]=Mn[1]=1; 9 for(int i=1;i<N;i++)fac[i]=(ll)fac[i-1]*i%mod; 10 for(int i=2;i<N;i++){ 11 if (!vis[i]){ 12 p[++p[0]]=i; 13 mx[i]=Mn[i]=i; 14 } 15 for(int j=1;(j<=p[0])&&(i*p[j]<N);j++){ 16 vis[i*p[j]]=1; 17 mx[i*p[j]]=mx[i]; 18 if (i%p[j])Mn[i*p[j]]=Mn[i]*p[j]; 19 else{ 20 Mn[i*p[j]]=Mn[i]; 21 break; 22 } 23 } 24 } 25 scanf("%d",&n); 26 for(int i=1;i<=n;i++)scanf("%d",&a[i]); 27 for(int i=1;i<=n;i++)cnt[Mn[i]]++; 28 f[1]=1; 29 for(int i=1,j;(i<=p[0])&&(p[i]<=n);i=j){ 30 j=i+1,f[p[i]]=p[i]; 31 while ((j<=p[0])&&(p[j]<=n)&&(n/p[i]==n/p[j]))f[p[j++]]=p[i]; 32 if ((j>p[0])||(p[j]>n)){ 33 for(int k=i;k<j;k++)f[p[k]]=1; 34 } 35 } 36 cnt0[1]++; 37 for(int i=1;(i<=p[0])&&(p[i]<=n);i++)cnt0[f[p[i]]]++; 38 for(int i=1;i<=n;i++) 39 if (a[i]){ 40 int x=i,y=a[i]; 41 cnt[Mn[y]]--; 42 if ((f[mx[x]]!=f[mx[y]])||(Mn[x]/mx[x]!=Mn[y]/mx[y])){ 43 printf("0 "); 44 return 0; 45 } 46 if ((x==1)||((ll)mx[x]*mx[x]>n)){ 47 if ((!r0[mx[x]])&&(!r1[mx[y]])){ 48 cnt0[f[mx[x]]]--; 49 r0[mx[x]]=mx[y],r1[mx[y]]=mx[x]; 50 } 51 if ((r0[mx[x]]!=mx[y])||(r1[mx[y]]!=mx[x])){ 52 printf("0 "); 53 return 0; 54 } 55 } 56 } 57 ans=1; 58 for(int i=1;i<=n;i++)ans=(ll)ans*fac[cnt[i]]%mod*fac[cnt0[i]]%mod; 59 printf("%d ",ans); 60 return 0; 61 }