結果
問題 |
No.732 3PrimeCounting
|
ユーザー |
![]() |
提出日時 | 2022-01-01 11:33:19 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 563 ms / 3,000 ms |
コード長 | 1,559 bytes |
コンパイル時間 | 1,417 ms |
コンパイル使用メモリ | 141,552 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-09 23:41:20 |
合計ジャッジ時間 | 8,667 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 89 |
ソースコード
#include <cassert> #include <cmath> #include <algorithm> #include <iostream> #include <iomanip> #include <limits.h> #include <map> #include <queue> #include <string.h> #include <vector> using namespace std; typedef long long ll; const ll MAX_N = 300000; bool is_prime[MAX_N + 1]; class Prime { public: vector<ll> prime_list; Prime(int n = MAX_N) { bool checked[n + 1]; memset(checked, false, sizeof(checked)); memset(is_prime, false, sizeof(is_prime)); for (ll i = 2; i <= n; ++i) { if (!checked[i]) { prime_list.push_back(i); is_prime[i] = true; for (ll j = i * i; j <= n; j += i) { checked[j] = true; } } } } map<ll, int> prime_division(ll n) { map<ll, int> res; for (ll i = 0; prime_list[i] <= sqrt(n); ++i) { ll p = prime_list[i]; while (n % p == 0) { ++res[p]; n /= p; } } if (n != 1) { res[n] = 1; } return res; } }; ll counter[300010]; int main() { memset(counter, 0, sizeof(counter)); int N; cin >> N; Prime prime(3 * N); int len = prime.prime_list.size(); ll ans = 0; counter[prime.prime_list[0] + prime.prime_list[1]]++; for (int i = 2; i < len && prime.prime_list[i] <= N; ++i) { int c = prime.prime_list[i]; for (int j = i + 1; j < len; ++j) { int d = prime.prime_list[j]; ans += counter[d - c]; } for (int j = 0; j < i; ++j) { int d = prime.prime_list[j]; counter[c + d]++; } } cout << ans << endl; return 0; }