permutations(找循环节).cpp

杭电acm解题报告2001---2099.

//从单位元，经过lcm(各循环节长度)次置换，重新回复单位元
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

int num[1100], n;
bool vis[1100];

int lcm(int x, int y)
{
	int t;
	__int64 mul = x*y;
	if(x > y) {
		std::swap(x,y);
	}
	while(x) {
		t = x;
		x = y%x;
		y = t;
	}
	return mul / y;
}

int main()
{
	int i, ans;
	while(scanf("%d", &n)==1) {
		for(i=1;i<=n;i++) {
			scanf("%d", num+i);
		}
		memset(vis,0,sizeof(vis));
		ans = 1;
		for(i=1;i<=n;i++) {
			if(!vis[i]) {
				int tpos = i;
				int len = 0;
				do {
					vis[tpos] = true;
					tpos = num[tpos];
					len ++;
				} while(tpos != i);
				ans = lcm(ans, len);
			}
		}
		printf("%d\n", ans);
	}
}