2487번: 섞기 수열

https://www.acmicpc.net/problem/2487


$O(n\lg C)$

모든 사이클 크기의 최소공배수를 구한다.

#include<cstdio>
int n, a[20001], ck[20001], r = 1;
int gcd(int x, int y) { return y ? gcd(y, x%y) : x; }
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    for (int i = 1; i <= n; i++) {
        int j = i, cnt = 0;
        for (; !ck[j]; j = a[j]) ck[j] = 1, cnt++;
        if (cnt) r = 1LL * r*cnt / gcd(r, cnt);
    }
    printf("%d", r);
    return 0;
}