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;
}