hihocoder 1330 数组变换

题目

链接 http://hihocoder.com/problemset/solution/1172843

给定一个 $1 - N$ 的排列 $P$,每次重排将第 $i$ 个元素放到第 $P_i$ 个位置上,例如 $P=(2,3,1)$,若初始数组是 $(1,2,3)$,重排一次后变为 $(3,1,2)$,重排三次后变回原数列。问给定一个置换,经过多少次回到原排列?

分析

这里要用到群论的一个结论:对于任意一个置换 $T$,若 $T^k = e$($e$ 为单位置换,即 $f(x) = x$,那么 $k$ 的最小整数解为 $T$ 的所有循环节长度的最小公倍数。

因此只需要遍历一遍 $T$,计算各个循环节长度,计算 LCM 即可。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 105;
int a[maxn], vis[maxn];
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a%b);
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
int main() {
    int n;
    while(~scanf("%d", &n)) {
        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        int res = 1;
        for(int i = 1; i <= n ; i++) {
            int cnt = 0;
            if(!vis[i]) {
                int p = i;
                while(!vis[p]) {
                    vis[p] = 1;
                    p = a[p];
                    cnt++;
                }
                res = lcm(res, cnt);
            }
        }
        printf("%d\n", res);
    }
}