POJ-2369, Timus-1024 : Permutations

問題概要

置換σ(N<1000)が与えられる。σ^k=ιになるような最小のkを求める問題。

解法

各iについて、何乗したら戻ってくるかを求めてそれの最小公倍数が答えになる。

acceptされたコード

計算量O(N^2*log N)。Timusは__gcdが使えなかった。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 1000;

int N;
int perm[MAX_N];

int lcm(int a, int b){
	return a/__gcd(a,b)*b;
}

void init(){
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%d", perm + i);
		perm[i]--;
	}
}

int solve(){
	int ans = 1;

	for(int i=0; i<N; i++){
		int cur = i, cnt = 1;
		for(cur=perm[cur]; cur != i; cnt++, cur=perm[cur]);
		ans = lcm(ans, cnt);
	}

	return ans;
}

int main(){
	init();
	printf("%d\n", solve());

	return 0;
}