题目链接

题面:

题意:
给定一个全排列P ,问有多少个全排列经过0次或多次P变换能变成 1... n 1...n 1...n

题解:
转化为,初始序列 1... n 1...n 1...n 经过0次或者多次P变换能产生多少个不同的序列。
找出P中的环,求 l c m lcm lcm 即可。

代码:

def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)

def lcm(a,b):
    return a*b//gcd(a,b)

def main():
    n=int(input())
    a=list(map(int,input().split()))
    a.insert(0,0)
    b=[False for i in range(n+10)]
    ans=1
    for i in range(1,n+1):
        if b[i]:
            continue
        cnt=0
        x=int(i)
        while b[x]==False:
            b[x]=True
            x=a[x]
            cnt+=1
        ans=lcm(ans,cnt)
    print(ans)

main()