結果

問題 No.2620 Sieve of Coins
ユーザー suisen
提出日時 2024-01-27 01:04:29
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 41 ms / 2,000 ms
コード長 1,884 bytes
コンパイル時間 860 ms
コンパイル使用メモリ 82,196 KB
最終ジャッジ日時 2025-02-18 23:59:57
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <array>
#include <cmath>

template <int M>
struct Mobius {
    std::array<int, M + 1> mobius;
    Mobius() : mobius{} {
        mobius[1] = 1;
        std::array<bool, M + 1> sieve;
        sieve.fill(1);
        for (int p = 2; p <= M; ++p) if (sieve[p]) {
            for (int v = M / p, vp = v * p; v; --v, vp -= p) {
                mobius[vp] = -mobius[v], sieve[vp] = false;
            }
        }
    }
    int operator[](int i) const { return mobius[i]; }
};

constexpr int M = 1000000;
constexpr int MAX_LOG2 = 39, MAX_LOG3 = 25;

long long count_square_2_3_free(long long n) {
    static Mobius<M> mobius;
    const int q = std::sqrt(n);
    long long res = 0;
    for (int i = 1; i <= q; i += 6) if (mobius[i]) {
        double d = n / (double(i) * i);
        long long v1 = (d + 1) / 6;
        long long v5 = (d + 5) / 6;
        res += mobius[i] * (v1 + v5);
    }
    for (int i = 5; i <= q; i += 6) if (mobius[i]) {
        double d = n / (double(i) * i);
        long long v1 = (d + 1) / 6;
        long long v5 = (d + 5) / 6;
        res += mobius[i] * (v1 + v5);
    }
    return res;
}

#include <iostream>

int main() {
    long long l;
    int n;
    std::cin >> l >> n;

    std::array<std::array<bool, MAX_LOG3 + 2>, MAX_LOG2 + 2> cnt{};
    for (int i = 0; i < n; ++i) {
        long long x;
        std::cin >> x;
        int e2 = 0, e3 = 0;
        for (long long v = x; v % 2 == 0; v /= 2) ++e2;
        for (long long v = x; v % 3 == 0; v /= 3) ++e3;
        for (int f : { 0, 1 }) for (int g : { 0, 1 }) cnt[e2 + f][e3 + g] ^= 1;
    }

    long long ans = 0;

    long long p2 = 1;
    for (int e2 = 0; e2 <= MAX_LOG2; ++e2, p2 *= 2) {
        long long p3 = 1;
        for (int e3 = 0; e3 <= MAX_LOG3; ++e3, p3 *= 3) {
            if (cnt[e2][e3]) ans += count_square_2_3_free(l / (p2 * p3));
        }
    }

    std::cout << ans << '\n';
}
0