結果
問題 |
No.732 3PrimeCounting
|
ユーザー |
|
提出日時 | 2018-09-10 15:25:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,090 ms / 3,000 ms |
コード長 | 2,777 bytes |
コンパイル時間 | 1,103 ms |
コンパイル使用メモリ | 94,716 KB |
実行使用メモリ | 32,412 KB |
最終ジャッジ日時 | 2024-12-29 20:16:36 |
合計ジャッジ時間 | 18,838 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 89 |
ソースコード
#include <cmath> #include <iostream> #include <map> #include <vector> using namespace std; using i64 = int64_t; using u64 = uint64_t; using u128 = __uint128_t; constexpr u64 O = 5, M = (1ULL << 51) * 509 + 1, M2 = -(M - 2), R2 = u64(-__uint128_t(M) % M); inline u64 MR(const __uint128_t &x) { u64 y = u64(x >> 64) - u64((__uint128_t(u64(x) * M2) * M) >> 64); return i64(y) < 0 ? y + M : y; } inline u64 init(const u64 &x) { return MR(__uint128_t(x) * R2); } inline u64 mod_mul(const u64 &x, const u64 &y, const u64 &unused) { return MR(__uint128_t(x) * y); } map<pair<u64, u64>, u64> cache; inline u64 mod_pow(u64 a, u64 n, const u64 &m) { auto key = make_pair(a, n); if(cache.count(key)) { return cache[key]; } u64 res = init(1); for(; n; n>>=1) { if(n & 1) { res = mod_mul(res, a, m); } a = mod_mul(a, a, m); } return cache[key] = res; } void myfmt(vector<u64> &a, bool inv) { int n = static_cast<int>(a.size()); if(n == 1) { return; } int m = n / 2; vector<u64> a0(m), a1(m); for(int i=0, j=0; i<m; ++i) { a0[i] = a[j++]; a1[i] = a[j++]; } myfmt(a0, inv); myfmt(a1, inv); u64 z = mod_pow(init(O), (M-1)/n, M); if(inv) { z = mod_pow(z, M-2, M); } u64 pz = init(1); for(int i=0; i<n; ++i) { a[i] = a0[i%m] + mod_mul(pz, a1[i%m], M); if(a[i] >= M) { a[i] -= M; } pz = mod_mul(pz, z, M); } } void fmt(vector<u64> &a) { myfmt(a, false); } void ifmt(vector<u64> &a) { myfmt(a, true); int n = static_cast<int>(a.size()); i64 inv = mod_pow(init(n), M-2, M); for(int i=0; i<n; ++i) { a[i] = mod_mul(a[i], inv, M); } } vector<u64> convol(vector<u64> a, vector<u64> b) { int n = 1; while(n < a.size() + b.size()) { n <<= 1; } a.resize(n); b.resize(n); fmt(a); fmt(b); vector<u64> c(n); for(int i=0; i<n; ++i) { c[i] = mod_mul(a[i], b[i], M); } ifmt(c); return c; } template <class Int> vector<bool> sieve(Int n) { vector<bool> is_prime(n+1, true); is_prime[0] = is_prime[1] = false; Int sq = Int(sqrt(n)); for(Int i=2; i<=sq; ++i) { if(is_prime[i]) { for(Int j=i*i; j<=n; j+=i) { is_prime[j] = false; } } } return is_prime; } int main(void) { int n; scanf("%d", &n); vector<bool> is_prime = sieve(n*3+1); vector<u64> c1(n+1), d2(n*2+1); for(int p=0; p<=n; ++p) { if(is_prime[p]) { ++c1[p]; ++d2[p*2]; } } for(auto &x : c1) { x = init(x); } for(auto &x : d2) { x = init(x); } vector<u64> c2 = convol(c1, c1), c3 = convol(c2, c1), d3 = convol(d2, c1); u64 res = 0; for(int p=0; p<=n*3; ++p) { if(is_prime[p]) { res += (MR(c3[p]) - MR(d3[p]) * 3) / 6; } } printf("%lu\n", res); return 0; }