[POJ2369]Permutations

置换群，求出循环节长度即可。
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 const int maxn = 1111;
 8 int n;
 9 int p[maxn];
10 bool vis[maxn];
11 
12 inline int gcd(int a, int b) {
13     return b == 0 ? a : gcd(b, a % b);
14 }
15 
16 int solve() {
17     memset(vis, false ,sizeof(vis));
18     int ans = 1;
19     int len;
20     int k;
21     for(int i = 1; i <= n; i++) {
22         if(!vis[i]) {
23             k = i;
24             len = 0;
25             while(!vis[k]) {
26                 len++;
27                 vis[k] = true;
28                 k = p[k];
29             }
30         }
31         ans = ans / gcd(ans, len) * len;
32     }
33     printf("%d
",ans);
34 }
35 
36 int main() {
37     scanf("%d", &n);
38     for(int i = 1; i <= n; i++) {
39         scanf("%d", &p[i]);
40     }
41     solve();
42 }