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