Codeforces #383 Div1 A. Arpa's loud Owf and Mehrdad's evil plan

なんかC早解きで大幅にレートが上がってIGMになった。解く力はあまり上がってないので実感はない。
http://codeforces.com/contest/741/problem/A

問題

N頂点N有向辺のグラフがある。
i番の点はC[i]番の点に有向辺を張っている。

各頂点から、有向辺に沿ってT回移動することを考える。
各頂点頂点XからT回移動した到達点をYとしたとき、YからT回移動した場合にXに戻ってくるようにしたい。

最小のTを求めよ。

解法

まず全頂点が閉路上にない場合解はなし。
それ以外の場合、全頂点における移動回数の周期を求め、その最大公約数をAとすると、それが解。
ただし、Aが偶数なら半分にする。

int N;
int C[1010];
int P[1010];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>C[i], C[i]--;
	
	ll ret=1;
	FOR(i,N) {
		int cur=i;
		FOR(j,N+2) {
			cur=C[cur];
			if(cur==i) {
				P[i]=j+1;
				break;
			}
		}
		if(j==N+2) return _P("-1\n");
		
		if(P[i]%2==0) P[i]/=2;
		ret=ret/__gcd(ret,(ll)P[i])*P[i];
	}
	cout<<ret<<endl;
	
}

まとめ

まぁこれは定番か。