[KOI'09] 섞기 수열

 문제는 여기에서 확인 가능하다.

---

 permutation이 주어졌을때, 이것을 최소 몇 번 합성하면 identity permutation이 되는가를 묻는 문제로, disjoint cycle을 모두 찾아주고, 찾은 cycle들의 length의 최소공배수가 섞기 수열의 궤적이 된다.

 예를 들어서 섞기 수열이 $(3\;2\;5\;6\;1\;4)$로 주어져있다고 하면, 원래의 수열 $(1\;2\;3\;4\;5\;6)$에서 1은 3과 5를 거쳐서 1로 돌아오고, 2는 항상 제자리에, 4는 6을 거쳐서 다시 제자리로 돌아오게 된다. 따라서 주어진 섞기 수열의 disjoint cycle은 $(3\;5\;1)$, $(2)$, $(6\;4)$임을 알 수 있고, 첫번째 cycle은 3번마다, 세번째 cycle은 2번마다 제자리로 돌아오기 때문에, $lcm(3, 2) = 6$이 섞기 수열의 궤적이 된다.

 코드는 아래와 같다.

#include<bits/stdc++.h>
 
using namespace std;
 
int N, m[20001], c[20001];
 
vector<int> cycle;
 
int gcd(int a, int b) {
    int tmp, n;
    while(b != 0) {
        n = a%b;
        a = b;
        b = n;
    }
    return a;
}
 
int solve(vector<int> num) {
    int s = num.size(), ans = num[0], a = 0, h, l;
    for(int i = 1; i < s; i++) {
        a = num[i];
        h = max(ans, a);
        l = min(a, ans);
        ans = h * (l / gcd(h, l));
    }
    return ans;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for(int i = 1; i <= N; i++) cin >> m[i];
    for(int i = 1; i <= N; i++) {
        if(c[i]) continue;
        c[i] = 1;
        int x = m[i], cnt = 1;
        while(x != i) {
            c[x] = 1;
            x = m[x];
            cnt++;
        }
        if(cnt != 1) cycle.push_back(cnt);
    }
    sort(cycle.begin(), cycle.end());
    cout << solve(cycle);
    return 0;
}