POJ 2369-Permutations Permutations Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 2792 Accepted: 1473 Description We remind that the permutation of some final set is a one-to-one mapping of the set onto itself. Less formally, that is a way to reorder elements of the set. For example, one can define a permutation of the set {1,2,3,4,5} as follows: This record defines a permutation P as follows: P(1) = 4, P(2) = 1, P(3) = 5, etc. What is the value of the expression P(P(1))? It’s clear, that P(P(1)) = P(4) = 2. And P(P(3)) = P(5) = 3. One can easily see that if P(n) is a permutation then P(P(n)) is a permutation as well. In our example (believe us) It is natural to denote this permutation by P2(n) = P(P(n)). In a general form the defenition is as follows: P(n) = P1(n), Pk(n) = P(Pk-1(n)). Among the permutations there is a very important one — that moves nothing: It is clear that for every k the following relation is satisfied: (EN)k = EN. The following less trivial statement is correct (we won’t prove it here, you may prove it yourself incidentally): Let P(n) be some permutation of an N elements set. Then there exists a natural number k, that Pk = EN. The least natural k such that Pk = EN is called an order of the permutation P. The problem that your program should solve is formulated now in a very simple manner: “Given a permutation find its order.” Input In the first line of the standard input an only natural number N (1 <= N <= 1000) is contained, that is a number of elements in the set that is rearranged by this permutation. In the second line there are N natural numbers of the range from 1 up to N, separated by a space, that define a permutation — the numbers P(1), P(2),…, P(N). Output You should write an only natural number to the standard output, that is an order of the permutation. You may consider that an answer shouldn’t exceed 109. Sample Input 5 4 1 5 2 3 Sample Output 6 Source Ural State University Internal Contest October’2000 Junior Session

---

有一个序列和一个置换T，问对这个序列置换多少次能恢复成原来的序列。这其实就是求置换群T的秩k使得$$T^k=e$$，e为单位置换f(x)=x。 在离散数学中有一个定理，k等于T中所有循环节长度的最小公倍数。 比如题中的P(n)有1->4->2->1，则循环节长度就为3，以及3->5->3，循环节长度为2，则最小公倍数为lcm(3,2)=6，即k=6。 设x,y的最小公倍数为lcm(x,y)，最大公约数为gcd(x,y)，则有gcd(x, y)×lcm(x, y) = xy，挺神奇的，所以求最小公倍数可以转换为求最大公约数。 完整代码如下： [cpp] #define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<cstdio> using namespace std; const int kMaxN = 1005; bool visited[kMaxN]; int permutation[kMaxN]; //最大公约数 int gcd(int x, int y) { int tmp; while (y) { tmp = y; y = x % y; x = tmp; } return x; } int main() { int n,ans,len; while (scanf("%d", &n)!=EOF) { ans = 1; memset(visited, false, n + 1); for (int i = 1; i <= n; i++) scanf("%d", &permutation[i]); for (int i = 1; i <= n; i++) { if (!visited[i]) { visited[i] = true; int j = permutation[i]; len = 1; while (j!=i) { visited[j] = true; j = permutation[j]; len++; } ans = len*ans/gcd(ans, len);//gcd(a, b)×lcm(a, b) = ab } } printf("%dn", ans); } return 0; } [/cpp] 本代码提交AC，用时0MS，内存136K。]]>