poj2369 Permutations ——置换群

August 24, 2013

置换群，最简单的那种。

找所有数字循环节的最小公倍数。

/*
ID: zypz4571
LANG: C++
TASK: permutations.cpp
 */

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <queue>
#include <deque>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <functional>
#include <fstream>
#include <iomanip>
#include <sstream>
#include <numeric>
#include <cassert>
#include <ctime>
#include <iterator>
const int INF = 0x3f3f3f3f;
const int dir[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
using namespace std;
int a[1111];
bool flag[1111];
int gcd(int x, int y) {
    return y == 0 ? x : gcd(y, x%y);
}
int lcm(int x, int y) {
    return x/gcd(x,y)*y;
}
int main ( int argc, char *argv[] )
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    int n;
    while (~scanf("%d", &n)) {
        for (int i = 0; i < n; ++i) scanf("%d", a+i+1);
        int ans = 1;
        memset(flag, false, sizeof(flag));
        for (int i = 1; i <= n; ++i) {
            int sum = 0, pos = i;
            if (!flag[pos]) {
                for (; !flag[a[pos]]; ++sum) {
                    flag[a[pos]] = true;
                    pos = a[pos];
                }
                ans = lcm(ans, sum);
            }
        }
        printf("%d\n", ans);
    }
        return EXIT_SUCCESS;
}                /* ----------  end of function main  ---------- */

开始有一点不理解，仔细想一想就明白了。把上面的程序模拟一下这个样例：

比如，我在对1找循环节的时候，过程中出现了4，那么将来，就不用对4找循环节了。

这么想：1 经过4到达1，那么4一定可以经过1到达4.并且4的循环节必然和1相等！

因为在对1找循环节的时候，你遇到了4，那么这就相当于在这个时候对4找循环节么。很神奇的样子。

多多模拟一下，严格的证明貌似还要好好看一下近世代数。

嗨，中村

Read more