結果

問題 No.8079 アルベド
ユーザー nonamae
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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';
    }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0