結果

問題 No.2620 Sieve of Coins
ユーザー suisen
提出日時 2024-01-27 00:19:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 39 ms / 2,000 ms
コード長 2,047 bytes
コンパイル時間 811 ms
コンパイル使用メモリ 85,124 KB
最終ジャッジ日時 2025-02-18 23:53:49
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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<int, M + 1> not_prime{};
        for (int p = 2; p <= M; ++p) {
            if (not_prime[p]) continue;
            for (int v = M / p, vp = v * p; v; --v, vp -= p) {
                mobius[vp] = -mobius[v];
                not_prime[vp] = true;
            }
        }
    }
    int operator[](int i) const { return mobius[i]; }
};

constexpr int M = 1000000;
Mobius<M> mobius;

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

#include <iostream>
#include <vector>

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

    std::array<std::array<bool, 30>, 40> cnt{};
    for (int i = 0; i < n; ++i) {
        long long e;
        std::cin >> e;
        int p2 = 0, p3 = 0;
        while (e % 2 == 0) e /= 2, ++p2;
        while (e % 3 == 0) e /= 3, ++p3;
        cnt[p2][p3] = true;
    }

    long long ans = 0;
    for (int p2 = 0; p2 < 40; ++p2) for (int p3 = 0; p3 < 30; ++p3) {
        int x00 = cnt[p2][p3];
        int x10 = p2 and cnt[p2 - 1][p3];
        int x01 = p3 and cnt[p2][p3 - 1];
        int x11 = p2 and p3 and cnt[p2 - 1][p3 - 1];

        if (x00 xor x01 xor x10 xor x11) {
            long long v = 1;
            for (int e = p2; e--;) v *= 2;
            for (int e = p3; e--;) v *= 3;
            long long lim = l / v;
            ans += count_square_2_3_free(lim);
        }
    }
    std::cout << ans << '\n';
}
0