698F: Coprime Permutation
素因数→素因数の写像が何通りあるかと、それぞれの素因数内で数の並べ方が何通りあるか掛け算する。
前者は、同じ回数出現する素因数が自由に入れ替えられるので、それぞれの素因数に対して、indexにその素因数をもつ場所のgcdを求めて、対応をつけると自由度がわかので階乗をかける。
後者は、(素因数の集合)ごとに独立で、これも前計算してから同様に自由度を求めて階乗をかける。
でも証明はできていない。
#include<stdio.h> #include<math.h> #include<algorithm> #include<queue> #include<string> #include<string.h> #include<vector> #include<set> #include<map> #include<stdlib.h> using namespace std; const long long mod=1000000007; const long long inf=mod*mod; int b[1100000]; int pr[1100000]; int st[1100000]; int to[1100000]; int val[1100000]; int wk[1100000]; int tk[1100000]; long long fact[1100000]; long long gcd(long long a,long long b){ while(a){ b%=a;swap(a,b); } return b; } int pl[110000]; int dec[1100000]; int used[1100000]; vector<int> pp[1100000]; int main(){ int a;scanf("%d",&a); fact[0]=1; for(int i=1;i<1100000;i++)fact[i]=fact[i-1]*i%mod; for(int i=0;i<a;i++){ scanf("%d",b+i); } pr[0]=pr[1]=-1; for(int i=2;i<1100000;i++){ if(pr[i]==-1)continue; pr[i]=1; for(int j=i+i;j<1100000;j+=i)pr[j]=-1; } st[1]++; for(int i=2;i<=a;i++){ if(pr[i]==1){ st[a/i]++; for(int j=i;j<=a;j+=i)pp[j].push_back(i); } } int ind=0; for(int i=2;i<1100000;i++){ if(pr[i]==1)pl[ind++]=i; } long long ret=1; if(pr[b[0]]==1||b[0]==1){ used[b[0]]=1; dec[1]++; } for(int i=1;i<=a;i++){ if(pr[i]==1){ int now=0; for(int j=i;j<=a;j+=i){ if(!b[j-1])continue; now=gcd(now,b[j-1]); } if(now!=0){ bool ok=false; int ss=-1; for(int j=0;j<pp[now].size();j++){ if(a/pp[now][j]==a/i){ ss=pp[now][j]; ok=true;break; } } if(!ok&&a/i==1&&now==1){ ss=now; ok=true; } // printf("%d: %d %d\n",i,now,ss); if(used[ss]||!ok){ printf("0\n");return 0; } used[ss]=1; dec[a/i]++; } } } for(int i=1;i<=a;i++)ret=ret*fact[st[i]-dec[i]]%mod; for(int i=1;i<=a;i++)val[i]=1; for(int i=2;i<=a;i++){ if(pr[i]==1){ for(int j=i;j<=a;j+=i)val[j]*=i; } } for(int i=1;i<=a;i++)wk[val[i]]++; for(int i=0;i<a;i++){ if(b[i])tk[val[b[i]]]++; } for(int i=1;i<=a;i++)ret=ret*fact[wk[i]-tk[i]]%mod; printf("%I64d\n",ret); }