Permutations
题目:http://poj.org/problem?id=2369
题意:
题解:置换群。求子循环节的长度,然后求其最小公倍数。
代码:
#include<cstdio> #include<cstring> using namespace std; int ans[1005]; bool visit[1005]; int gcd(int x,int b) { int c; for(; b!=0;) { c=x%b; x=b; b=c; } return x; } int main() { int n,len,res; for(;~scanf("%d",&n);) { for(int i=1;i<=n;++i) scanf("%d",ans+i); memset(visit,false,sizeof(visit)); res=1; for(int i=1; i<=n; ++i) { if(!visit[i]) { len=0; int t=i; for(;;) { if(visit[t]) break; len++; visit[t]=true; t=ans[t]; } res=res/gcd(len,res)*len; } } printf("%d\n",res); } return 0; }