2369 Permutations
問題概要
nの順列とは、1〜nの数字が一度ずつ表れる数列のことを言う。
P(i)を順列のk番目の文字とする。
P1(i)=P(i),P2(i)=P(P(i)),P3(i)=P(P(P(i)))…と定義する。
nの順列が与えられるとき、
Pk(1),Pk(2),…,Pk(n)がもとの順列に一致するような最小のkを求めよ。
n≦1000を満たす。
解法
1からはじめてP(1)→P(P(1))→……と繰り返しPを適用していくと、いつか1にもどる。
このようなループの長さを全数字に対して求める。
それらの最小公倍数が求めるkである。
ソースコード
int n,a[1000]; bool v[1000]; int rec(int c){ v[c]=1; return v[a[c]]?1:1+rec(a[c]); } int main() { scanf("%d",&n); rep(i,n)scanf("%d",a+i),a[i]--; ll ans=1; rep(i,n)if(!v[i]){ int l=rec(i); ans=ans*l/__gcd(ans,ll(l)); } printf("%lld\n",ans); return 0; }