結果
問題 | No.732 3PrimeCounting |
ユーザー | Pachicobue |
提出日時 | 2018-09-07 21:48:34 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,964 ms / 3,000 ms |
コード長 | 4,264 bytes |
コンパイル時間 | 2,640 ms |
コンパイル使用メモリ | 208,428 KB |
実行使用メモリ | 77,616 KB |
最終ジャッジ日時 | 2023-08-19 18:04:56 |
合計ジャッジ時間 | 30,082 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,376 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 2 ms
4,376 KB |
testcase_09 | AC | 1 ms
4,380 KB |
testcase_10 | AC | 2 ms
4,380 KB |
testcase_11 | AC | 2 ms
4,376 KB |
testcase_12 | AC | 2 ms
4,384 KB |
testcase_13 | AC | 2 ms
4,380 KB |
testcase_14 | AC | 2 ms
4,384 KB |
testcase_15 | AC | 2 ms
4,384 KB |
testcase_16 | AC | 2 ms
4,376 KB |
testcase_17 | AC | 2 ms
4,376 KB |
testcase_18 | AC | 2 ms
4,380 KB |
testcase_19 | AC | 2 ms
4,380 KB |
testcase_20 | AC | 7 ms
4,380 KB |
testcase_21 | AC | 25 ms
4,740 KB |
testcase_22 | AC | 25 ms
4,764 KB |
testcase_23 | AC | 4 ms
4,380 KB |
testcase_24 | AC | 3 ms
4,376 KB |
testcase_25 | AC | 51 ms
5,904 KB |
testcase_26 | AC | 42 ms
5,816 KB |
testcase_27 | AC | 11 ms
4,376 KB |
testcase_28 | AC | 11 ms
4,376 KB |
testcase_29 | AC | 21 ms
4,772 KB |
testcase_30 | AC | 21 ms
4,808 KB |
testcase_31 | AC | 25 ms
4,748 KB |
testcase_32 | AC | 42 ms
5,960 KB |
testcase_33 | AC | 42 ms
5,888 KB |
testcase_34 | AC | 42 ms
5,784 KB |
testcase_35 | AC | 42 ms
5,728 KB |
testcase_36 | AC | 42 ms
6,044 KB |
testcase_37 | AC | 6 ms
4,376 KB |
testcase_38 | AC | 6 ms
4,376 KB |
testcase_39 | AC | 42 ms
5,920 KB |
testcase_40 | AC | 25 ms
4,692 KB |
testcase_41 | AC | 25 ms
4,828 KB |
testcase_42 | AC | 24 ms
4,784 KB |
testcase_43 | AC | 25 ms
4,820 KB |
testcase_44 | AC | 24 ms
4,664 KB |
testcase_45 | AC | 13 ms
4,380 KB |
testcase_46 | AC | 13 ms
4,380 KB |
testcase_47 | AC | 21 ms
4,612 KB |
testcase_48 | AC | 50 ms
5,888 KB |
testcase_49 | AC | 50 ms
5,964 KB |
testcase_50 | AC | 25 ms
4,816 KB |
testcase_51 | AC | 25 ms
4,768 KB |
testcase_52 | AC | 11 ms
4,384 KB |
testcase_53 | AC | 103 ms
8,480 KB |
testcase_54 | AC | 812 ms
40,872 KB |
testcase_55 | AC | 822 ms
41,196 KB |
testcase_56 | AC | 841 ms
40,968 KB |
testcase_57 | AC | 224 ms
13,420 KB |
testcase_58 | AC | 229 ms
13,428 KB |
testcase_59 | AC | 106 ms
8,576 KB |
testcase_60 | AC | 381 ms
21,888 KB |
testcase_61 | AC | 381 ms
22,028 KB |
testcase_62 | AC | 826 ms
41,932 KB |
testcase_63 | AC | 457 ms
23,220 KB |
testcase_64 | AC | 378 ms
22,592 KB |
testcase_65 | AC | 381 ms
22,636 KB |
testcase_66 | AC | 3 ms
4,380 KB |
testcase_67 | AC | 3 ms
4,376 KB |
testcase_68 | AC | 835 ms
41,192 KB |
testcase_69 | AC | 835 ms
41,100 KB |
testcase_70 | AC | 855 ms
40,964 KB |
testcase_71 | AC | 830 ms
41,120 KB |
testcase_72 | AC | 455 ms
23,148 KB |
testcase_73 | AC | 1,011 ms
43,476 KB |
testcase_74 | AC | 1,019 ms
43,604 KB |
testcase_75 | AC | 51 ms
5,812 KB |
testcase_76 | AC | 839 ms
41,232 KB |
testcase_77 | AC | 222 ms
13,384 KB |
testcase_78 | AC | 1,049 ms
42,460 KB |
testcase_79 | AC | 850 ms
41,264 KB |
testcase_80 | AC | 1,022 ms
42,104 KB |
testcase_81 | AC | 846 ms
40,952 KB |
testcase_82 | AC | 11 ms
4,376 KB |
testcase_83 | AC | 225 ms
13,460 KB |
testcase_84 | AC | 380 ms
21,792 KB |
testcase_85 | AC | 855 ms
40,720 KB |
testcase_86 | AC | 1,049 ms
42,020 KB |
testcase_87 | AC | 1,943 ms
77,440 KB |
testcase_88 | AC | 1,964 ms
77,616 KB |
ソースコード
//================================= // Created on: 2018/09/07 21:33:10 //================================= #include <bits/stdc++.h> #define show(x) std::cerr << #x << " = " << x << std::endl using ll = long long; using ull = unsigned long long; using ld = long double; constexpr std::size_t PC(const ull v) { ull count = (v & 0x5555555555555555ULL) + ((v >> 1) & 0x5555555555555555ULL); count = (count & 0x3333333333333333ULL) + ((count >> 2) & 0x3333333333333333ULL); count = (count & 0x0f0f0f0f0f0f0f0fULL) + ((count >> 4) & 0x0f0f0f0f0f0f0f0fULL); count = (count & 0x00ff00ff00ff00ffULL) + ((count >> 8) & 0x00ff00ff00ff00ffULL); count = (count & 0x0000ffff0000ffffULL) + ((count >> 16) & 0x0000ffff0000ffffULL); return static_cast<std::size_t>((count & 0x00000000ffffffffULL) + ((count >> 32) & 0x00000000ffffffffULL)); } constexpr std::size_t LG(ull v) { return v == 0 ? 0 : (v--, v |= (v >> 1), v |= (v >> 2), v |= (v >> 4), v |= (v >> 8), v |= (v >> 16), v |= (v >> 32), PC(v)); } constexpr ull SZ(const ull v) { return 1ULL << LG(v); } class FastFourierTransformation { private: using T = ll; using F = ld; static constexpr F PI = static_cast<F>(3.141592653589793238462643383279502884); using P = std::pair<F, F>; static P plus(const P& c1, const P& c2) { return P{c1.first + c2.first, c1.second + c2.second}; } static P minus(const P& c1, const P& c2) { return P{c1.first - c2.first, c1.second - c2.second}; } static P mul(const P& c1, const P& c2) { return P{c1.first * c2.first - c1.second * c2.second, c1.first * c2.second + c1.second * c2.first}; } public: FastFourierTransformation() = delete; static std::vector<P> fft(std::vector<P>& a, const bool rev = false) { const std::size_t size = a.size(), height = LG(size); for (std::size_t i = 0; i < size; i++) { std::size_t j = 0; for (std::size_t k = 0; k < height; k++) { j |= (i >> k & 1) << (height - 1 - k); } if (i < j) { swap(a[i], a[j]); } } for (std::size_t i = 1; i < size; i <<= 1) { for (std::size_t j = 0; j < i; j++) { const F theta = 2 * PI / (F)(i << 1) * (F)(rev ? -1 : 1) * (F)j; const P w{std::cos(theta), std::sin(theta)}; for (std::size_t k = 0; k < size; k += (i << 1)) { const P s = a[j + k + 0], t = mul(a[j + k + i], w); a[j + k + 0] = P{s.first + t.first, s.second + t.second}, a[j + k + i] = P{s.first - t.first, s.second - t.second}; } } } if (not rev) { return a; } for (std::size_t i = 0; i < size; i++) { a[i].first /= (F)size, a[i].second /= (F)size; } return a; } static std::vector<T> convolute(const std::vector<T>& a, const std::vector<T>& b) // ans[i] = \sum_{A+B = i} a[A]*b[B] { const std::size_t size = a.size() + b.size() - 1, t = (std::size_t)SZ(size); std::vector<P> A(t), B(t); for (std::size_t i = 0; i < a.size(); i++) { A[i].first = (F)a[i]; } for (std::size_t i = 0; i < b.size(); i++) { B[i].first = (F)b[i]; } A = fft(A), B = fft(B); for (std::size_t i = 0; i < t; i++) { A[i] = mul(A[i], B[i]); } A = fft(A, true); std::vector<T> ans(size); for (std::size_t i = 0; i < size; i++) { ans[i] = (T)std::round(A[i].first); } return ans; } }; int main() { ll MAX; std::cin >> MAX; std::vector<ll> a(3 * MAX + 1, 1); for (ll i = 2; i <= 3 * MAX; i++) { if (not a[i]) { continue; } for (ll j = 2; i * j <= 3 * MAX; j++) { a[i * j] = false; } } a[0] = a[1] = 0; const auto A = a; a.resize(MAX + 1); const auto b = FastFourierTransformation::convolute(a, a); const auto c = FastFourierTransformation::convolute(a, b); ll ans = 0; for (ll i = 0; i <= 3 * MAX; i++) { if (A[i]) { ans += c[i]; } } std::vector<ll> B(2 * MAX + 1, 0); for (ll i = 0; i <= MAX; i++) { B[2 * i] = A[i]; } const auto C = FastFourierTransformation::convolute(B, a); for (ll i = 0; i <= 3 * MAX; i++) { if (A[i]) { ans -= 3 * C[i]; } } std::cout << ans / 6 << std::endl; return 0; }