一日一题（22）

链接：http://poj.org/problem?id=2369

图片.png

题意是求一个置换群的群阶。换句话说，求一个排列对自身最少置换几次之后能回到最初排列。

这里有一个比较惯常的思维：将排列，看做点向连边，点向连边...点向连边（边有向）。由于排列中每个元素都不相同，不可能有一个点入度比1大，也不可能入度为0。因此，这样构成的图，是由很多个简单环组成的。

每一次的置换，上的数字可以看做是在所在的环上移动了一次。因此，对于单个环而言，周期就是环的长度。对于所有环而言，周期就是环长的最小公倍数。

from math import gcd
n=int(input())
a=[0]+list(map(int,input().split()))
vis=[False]*(n+1)

ans=1
for i in range(1,n+1):
    if not vis[i]:
        Cir=0
        p=i
        while not vis[p]:
            vis[p]=True
            p=a[p]
            Cir+=1
        ans*=Cir//gcd(ans,Cir)

print(ans)