ural 1024 Permutations

这里要用到点组合的知识了.

引理: 对于P中任意元素i, 存在k, 使得P^k(i)=i.

然后就很好办了.

#include<iostream> const int MAXN=1000; int P[MAXN+1]; int has[MAXN+1]; int n,ans=1; int LCM(int i,int j) { int temp; if(i<j) { temp=i;i=j;j=temp; } if(i%j==0) return j; else return LCM(j,i%j); } int GCD(int i,int j) { return i*j/LCM(i,j); } int circle(int i) { int temp=P[i],tot=0; has[temp]=1; while(temp!=i) { temp=P[temp]; has[temp]=1; tot++; } return tot+1; } int main() { int i,j,k; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&P[i]); for(i=1;i<=n;i++) if(!has[i]) ans=GCD(ans,circle(i)); printf("%d/n",ans); return 0; }