算法:
对于第i个数,模拟计算出其置换周期,记为ai,答案就是所有ai的最小公倍数。
1 2 3 4 5
4 1 5 2 3
次数:3 3 2 3 2,最小公倍数6.
#include <iostream> #include <cstdio> int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a % b); } int lcm(int a, int b) { return a / gcd(a, b) * b; } int rota(int *f, int i) { int num = 1; int t = f[i]; while (f[i] != f[t]) { t = f[t]; ++num; } return num; } int main() { int n; scanf("%d", &n); int f[n+1]; for (int i = 1; i <= n; ++i) { scanf("%d", &f[i]); } int ans = 1; for (int i = 1; i <= n; ++i) { int num = rota(f, i); ans = lcm(ans, num); } printf("%d\n", ans); //system("pause"); return 0; }