結果
問題 |
No.8079 アルベド
|
ユーザー |
![]() |
提出日時 | 2022-07-12 12:35:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,127 ms / 2,000 ms |
コード長 | 1,021 bytes |
コンパイル時間 | 2,070 ms |
コンパイル使用メモリ | 197,356 KB |
最終ジャッジ日時 | 2025-01-30 06:42:55 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
#include <bits/stdc++.h> using namespace std; using u64 = uint_fast64_t; u64 count_primes(const u64 n) { auto v = (unsigned int)sqrt(n); vector<u64> higher(v + 2, 0); vector<unsigned int> lower(v + 2, 0); vector<bool> used(v + 2, false); u64 result = n - 1; for (unsigned int p = 2; p <= v; p++) { lower[p] = p - 1; higher[p] = n / p - 1; } for (unsigned int p = 2; p <= v; p++) { if (lower[p] == lower[p - 1]) continue; auto temp = lower[p - 1]; result -= higher[p] - temp; auto pxp = (u64) p * p; auto end = min<u64>(v, n / pxp); auto j = 1 + (p & 1); for (auto i = p + j; i <= end + 1; i += j) { if (used[i]) continue; auto d = i * p; if (d <= v) higher[i] -= higher[d] - temp; else higher[i] -= lower[n / d] - temp; } for (auto i = v; i >= pxp; i--) lower[i] -= lower[i / p] - temp; for (auto i = pxp; i <= end; i += p * j) used[i] = true; } return result; } int main() { u64 a, b; cin >> a; while (a--) { cin >> b; cout << count_primes(b) << '\n'; } }