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
此题和
POJ 2369-Permutations类似，只是测试样例更多，数据规模更大，最后还要对某个大数取模。所以在求所有循环节长度的最小公倍数的时候，不能使用gcd转换的方法，需要先后使用因式分解和快速幂算法。
参考下面的例子理解
分解质因数法求最小公倍数的方法。
60=
2×2×3×
5
18=2×
3×3
lcm(60,18)=180=2×2×3×3×5
通过观察可以看出规律，要求a,b的最小公倍数，先将a和b分解成质因数相乘的形式，对于每一个质因子x，取x在a和b中出现频率最高的数作为x在最小公倍数中的频率。比如2在60中出现2次，但在18中只出现1次，所以2在最小公倍数180中也出现2次，同理质因子3和5分别出现2次和1次。
假设某个质因子x出现y次，则最后要计算$$x^ymodp$$，可以使用快速幂方法提高速度，该方法很好理解，将y看成二进制形式，如果y为偶数，则$$x^y=(x*x)^{y/2}$$；如果y为奇数，则$$x^y=x*x^{y-1}$$，y-1就是偶数了。同时modp就是快速幂取模了。
完整代码如下：
[cpp]
#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;
}
[/cpp]
本代码提交AC，用时5101MS，内存27984K。]]>