首页 > 代码库 > poj 2369 Permutations(置换群)

poj 2369 Permutations(置换群)

题目链接:poj 2369 Permutations

题意:

给你一个置换序列,问你循环周期是多少。

题解:

找到每个子循环周期,总体的循环周期就是这些子循环周期的最小公倍数。

技术分享
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define F(i,a,b) for(int i=a;i<=b;++i)
 5 using namespace std;
 6 
 7 const int N=1010;
 8 int n,a[N],vis[N],Q[N],ed;
 9 
10 int main()
11 {
12     while(~scanf("%d",&n))
13     {
14         F(i,1,n)scanf("%d",a+i),vis[i]=0;
15         ed=0;
16         F(i,1,n)if(!vis[i])
17         {
18             vis[i]=1;
19             int cnt=1,u=a[i];
20             while(u!=i)cnt++,vis[u]=1,u=a[u];
21             Q[++ed]=cnt;
22         }
23         int ans=Q[1];
24         F(i,1,ed)ans=ans/__gcd(Q[i],ans)*Q[i];
25         printf("%d\n",ans);
26     }
27     return 0;
28 }
View Code

 

poj 2369 Permutations(置换群)