blob: 43a2b1abdd06943b7e266fc82a42b39ac36dc62b (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
|
#include <stdio.h>
#include <math.h>
#include <queue>
using namespace std;
int nprime;
int primes[501000];
#define MOD 500500507
/* b^(2^n-1) % MOD */
long long expmod(int b, int log2n)
{
long long rem = 1;
long long base = b;
for (int i = 0; i < log2n; i++) {
rem = rem * base % MOD;
base = base * base % MOD;
}
return rem;
}
void next_prime()
{
int t = primes[nprime-1];
while (1) {
t += 2;
int flag = 1;
for (int i = 0; primes[i] * primes[i] <= t; i++) {
if (t % primes[i] == 0) {
flag = 0;
break;
}
}
if (flag) {
primes[nprime] = t;
nprime++;
return;
}
}
}
void init()
{
primes[0] = 2;
primes[1] = 3;
nprime = 2;
}
class elem
{
public:
int idx;
double v;
elem(int i, double vv)
{
idx = i;
v = vv;
}
};
bool operator>(const elem& s, const elem& t)
{
return s.v > t.v;
}
int main()
{
static int npow[501000]; /* prime[i]^(2^npow[i] - 1) */
int log2ndiv = 500500;
long long result = 1;
init();
for (int i = 0; i <= nprime; i++)
npow[i] = 0;
priority_queue< elem, vector<elem>, greater<elem> > heap;
heap.push(elem(0, log2(2)));
while (log2ndiv) {
elem m = heap.top();
heap.pop();
if (npow[m.idx] == 0) {
npow[m.idx+1] = 0;
next_prime();
heap.push(elem(m.idx+1, log2(primes[m.idx+1])));
}
npow[m.idx] = npow[m.idx] + 1;
heap.push(elem(m.idx, m.v * 2));
log2ndiv--;
}
for (int i = 0; npow[i]; i++) {
result = result * expmod(primes[i], npow[i]) % MOD;
}
printf("%lld\n", result);
}
|