From 57db469caa62b1bf9a24f56348370d8138a62b10 Mon Sep 17 00:00:00 2001
From: Iru Cai <mytbk920423@gmail.com>
Date: Sat, 16 Jun 2018 16:12:47 +0800
Subject: 500

---
 euler500.cpp | 97 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 97 insertions(+)
 create mode 100644 euler500.cpp

diff --git a/euler500.cpp b/euler500.cpp
new file mode 100644
index 0000000..43a2b1a
--- /dev/null
+++ b/euler500.cpp
@@ -0,0 +1,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);
+}
-- 
cgit v1.2.3