题面:
题意:
给定一个全排列P ,问有多少个全排列经过0次或多次P变换能变成 1...n
题解:
转化为,初始序列 1...n 经过0次或者多次P变换能产生多少个不同的序列。
找出P中的环,求 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()