# HDOJ 5392-Infoplane in Tina Town

HDOJ 5392-Infoplane in Tina Town
Infoplane in Tina Town
Time Limit: 14000/7000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1636 Accepted Submission(s): 385
Problem Description
There is a big stone with smooth surface in Tina Town. When people go towards it, the stone surface will be lighted and show its usage. This stone was a legacy and also the center of Tina Town’s calculation and control system. also, it can display events in Tina Town and contents that pedestrians are interested in, and it can be used as public computer. It makes people’s life more convenient (especially for who forget to take a device).
Tina and Town were playing a game on this stone. First, a permutation of numbers from 1 to n were displayed on the stone. Town exchanged some numbers randomly and Town recorded this process by macros. Town asked Tine,”Do you know how many times it need to turn these numbers into the original permutation by executing this macro? Tina didn’t know the answer so she asked you to find out the answer for her.
Since the answer may be very large, you only need to output the answer modulo 3∗230+1=3221225473 (a prime).
Input
The first line is an integer T representing the number of test cases. T≤5
For each test case, the first line is an integer n representing the length of permutation. n≤3∗106
The second line contains n integers representing a permutation A1...An. It is guaranteed that numbers are different each other and all Ai satisfies ( 1≤Ai≤n ).
Output
For each test case, print a number ans representing the answer.
Sample Input
2
3
1 3 2
6
2 3 4 5 6 1
Sample Output
2
6
Source
BestCoder Round #51 (div.2)
Recommend
hujie | We have carefully selected several similar problems for you: 5395 5394 5393 5390 5389

60=2×2×3×5
18=2×3×3
lcm(60,18)=180=2×2×3×3×5

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned long long ULL;
const int kMaxN = 3000005, kNumPrime = 269;
const ULL kMod = 3221225473;
bool visited[kMaxN];
int permutation[kMaxN];
int prime[kNumPrime] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723 };
int prime_times[kMaxN];
//求x的所有质因子及其频率
void GetPrimeFactor(int x)
{
for (int i = 0; i < kNumPrime; i++)
{
int tmp = 0;
while (x%prime[i] == 0)
{
tmp++;
x /= prime[i];
}
if (tmp > prime_times[prime[i]])
prime_times[prime[i]] = tmp;
if (x == 1)
return;
}
prime_times[x]++;
}
//快速幂取模x^ymod(kMod)
ULL QuickPow(ULL x, ULL y)
{
ULL ans = 1;
while (y)
{
if (y & 1)
ans = (ans*x)%kMod;
x = (x*x) % kMod;
y >>= 1;
}
return ans;
}
int main()
{
int t, n, len;
ULL ans;
scanf("%d", &t);
while (t--)
{
scanf("%d", &n);
memset(visited, false, kMaxN);
memset(prime_times, 0, kMaxN);
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++;
}
GetPrimeFactor(len);
}
}
ans = 1;
for (int i = 2; i < n; i++)
if (prime_times[i] != 0)
ans = (ans*QuickPow(i, prime_times[i])) % kMod;
printf("%I64un", ans);
}
return 0;
}


# POJ 2369-Permutations

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

#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;
}