結果
問題 | No.732 3PrimeCounting |
ユーザー |
|
提出日時 | 2019-03-26 17:43:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 291 ms / 3,000 ms |
コード長 | 2,673 bytes |
コンパイル時間 | 1,378 ms |
コンパイル使用メモリ | 115,120 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-10-11 01:30:44 |
合計ジャッジ時間 | 6,481 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 89 |
ソースコード
// includes #include <cstdio> #include <cstdint> #include <iostream> #include <iomanip> #include <string> #include <queue> #include <stack> #include <vector> #include <set> #include <map> #include <unordered_map> #include <algorithm> #include <utility> #include <functional> #include <cmath> #include <climits> #include <bitset> #include <list> #include <random> // macros #define ll long long int #define pb emplace_back #define mk make_pair #define pq priority_queue #define FOR(i, a, b) for(int i=(a);i<(b);++i) #define rep(i, n) FOR(i, 0, n) #define rrep(i, n) for(int i=((int)(n)-1);i>=0;i--) #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()) using namespace std; // types typedef pair<int, int> P; typedef pair<ll, int> Pl; typedef pair<ll, ll> Pll; typedef pair<double, double> Pd; // constants const int inf = 1e9; const ll linf = 1LL << 50; const double EPS = 1e-10; const int mod = 1e9 + 7; // solve template <class T>bool chmax(T &a, const T &b){if(a < b){a = b; return 1;} return 0;} template <class T>bool chmin(T &a, const T &b){if(a > b){a = b; return 1;} return 0;} template <typename T> vector<T> list_prime(T n){ vector<T> res; vector<bool> i_prime = vector<bool>(n+1, true); for(ll i = 2; i <= n; i++){ if(i_prime[i]){ res.push_back(i); for(ll j = 2; j * i <= n; j++){ i_prime[i * j] = false; } } } return res; } template <typename T> T power(T a, T n, T mod) { T res = 1; T tmp = n; T curr = a; while(tmp){ if(tmp % 2 == 1){ res = (T)((ll)res * curr % mod); } curr = (T)((ll)curr * curr % mod); tmp >>= 1; } return res; } template <typename T> bool suspect(T a, int s, T d, T n){ T x = power<T>(a, d, n); if(x == 1)return true; for(int r = 0; r < s; r++){ if(x == n - 1)return true; x = x * x % n; } return false; } template <typename T> bool millar_rabin(T n){ if(n <= 1 || (n > 2 && n % 2 == 0))return false; vector<ll> test = {2, 3, 5, 7, 11, 13, 17, 19, 23}; T d = n - 1; int s = 0; while(d % 2 == 0)s++, d /= 2; for(int i = 0; i < test.size() && test[i] < n; i++){ if(!suspect<T>(test[i], s, d, n))return false; } return true; } ll cnt[300001]; int main(int argc, char const* argv[]) { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; auto p = list_prime(3 * n); ll res = 0; for(int i = 0; p[i] <= n; i++){ for(int j = i + 1; j < sz(p); j++){ int tmp = p[j] - p[i]; res += cnt[tmp]; } for(int j = 0; j < i; j++){ cnt[p[i] + p[j]]++; } } cout << res << endl; return 0; }