だいぶ前だけど書かないと忘れるから書いてしまおう。
http://codeforces.com/contest/542/problem/C
問題
{1..n}の整数からなる集合に対し関数gが冪等であるとは、x∈{1..n}に対しg(x)∈{1..n}であり、かつg(g(x))=g(x)となるものをいう。
{1..n}から{1..n}に変換する関数fが与えられる。f^n(x)が冪等となるような最小のnを求めよ。
解法
x∈{1..n}に対しfを繰り返し適用していくといずれループに突入する。
各xに対しこのループの周期と、最初にループに入る最小のfの適用回数を求める。
最終的な解は、全xにおけるループ周期の公倍数のうち、全xでループに突入する最小値を求めたものとなる。
int N; int F[300]; ll fir[300],per[300]; ll ret=1; ll maf; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; for(i=1;i<=N;i++) cin>>F[i]; for(i=1;i<=N;i++) { int ind[300]={}; MINUS(ind); x=0; y=i; ind[i]=0; while(1) { x++; y=F[y]; if(ind[y]>=0) { fir[i]=ind[y]; per[i]=x-ind[y]; break; } ind[y]=x; } fir[i]=(fir[i]+per[i]-1)/per[i]*per[i]; maf = max(maf,fir[i]); ret = per[i]*(ret/__gcd(ret,per[i])); } ll tmp=ret; while(ret<maf) ret+=tmp; cout<<ret<<endl; }
まとめ
これは割と典型っぽいかも。