diff options
| -rw-r--r-- | euler500.cpp | 97 |
1 files changed, 97 insertions, 0 deletions
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); +} |