結果
問題 | No.8079 アルベド |
ユーザー | nonamae |
提出日時 | 2022-07-12 10:37:54 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,204 bytes |
コンパイル時間 | 1,962 ms |
コンパイル使用メモリ | 204,828 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-23 06:07:48 |
合計ジャッジ時間 | 4,497 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | RE | - |
testcase_01 | RE | - |
testcase_02 | RE | - |
testcase_03 | RE | - |
testcase_04 | RE | - |
testcase_05 | RE | - |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | RE | - |
testcase_09 | RE | - |
コンパイルメッセージ
main.cpp: In function 'u64 prime_counting(u64)': main.cpp:45:13: warning: '*larges[0]' may be used uninitialized [-Wmaybe-uninitialized] 45 | larges[0] += (i64)(s + 2 * (pc - 1)) * (s - 1) / 2; | ~~~~~~~~^
ソースコード
#include <bits/stdc++.h>using i64 = std::int64_t;using u64 = std::uint64_t;u64 prime_counting(u64 n) {if (n == 0) return n;if (n <= 3) return n - 1;const int v = sqrtl(n);int s = (v + 1) / 2;int smalls[s]; for (int i = 1; i < s; i++) smalls[i] = i;int roughs[s]; for (int i = 0; i < s; i++) roughs[i] = 2 * i + 1;i64 larges[s]; for (int i = 0; i < s; i++) larges[i] = (n / (2 * i + 1) - 1) / 2;bool skip[v + 1];#define DIVIDE(n, d) ((int)((double)(n)/d))#define HALF(n) (((n)-(1))>>(1))int pc = 0;for (int p = 3; p <= v; p += 2) if (!skip[p]) {int q = p * p;if ((i64)q * q > n) break;skip[p] = true;for (int i = q; i <= v; i += 2 * p) skip[i] = true;int ns = 0;for (int k = 0; k < s; k++) {int i = roughs[k];if (skip[i]) continue;i64 d = (i64)i * p;larges[ns] = larges[k] - (d <= v ? larges[smalls[d >> 1] - pc] : smalls[HALF(DIVIDE(n, d))]) + pc;roughs[ns++] = i;}s = ns;for (int i = HALF(v), j = ((v / p) - 1) | 1; j >= p; j -= 2) {int c = smalls[j >> 1] - pc;for (int e = (j * p) >> 1; i >= e; i--) smalls[i] -= c;}pc++;}larges[0] += (i64)(s + 2 * (pc - 1)) * (s - 1) / 2;for (int k = 1; k < s; k++) larges[0] -= larges[k];for (int l = 1; l < s; l++) {i64 q = roughs[l];i64 M = n / q;int e = smalls[HALF(M / q)] - pc;if (e < l + 1) break;i64 t = 0;for (int k = l + 1; k <= e; k++) t += smalls[HALF(DIVIDE(M, roughs[k]))];larges[0] += t - (i64)(e - l) * (pc + l - 1);}#undef DIVIDE#undef HALFreturn larges[0] + 1;}u64 in_u64(void) {u64 c, x = 0;while (c = getchar_unlocked(), c < 48 || c > 57);while (47 < c && c < 58) {x = x * 10 + c - 48;c = getchar_unlocked();}return x;}int main() {u64 T;std::cin >> T;while (T--) {u64 x;std::cin >> x;std::cout << prime_counting(x) << '\n';}std::cout << std::flush;}