PKU 2369 Permutations
http://poj.org/problem?id=2369
数字の置き換えPが与えられる。数字が順番に並んでいる列Eに対して、何回Pを適用するとEに戻ってくるかを答えるというような問題。
それぞれの数字が元の位置に戻ってくるのに必要な周期を求めて、その最小公倍数を取りました。
入力のデクリメントを忘れて1WA。
int in[1000]; bool vis[1000]; int dfs(int v){ if(vis[v])return 1; vis[v]=true; return dfs(in[v])+1; } main(){ int n; cin>>n; rep(i,n){ cin>>in[i]; --in[i]; } ll ans=1; rep(i,n){ if(vis[i])continue; ll cy=dfs(i)-1; ans=cy*ans/__gcd(cy,ans); } cout<<ans<<endl; }