euler500.cpp


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