結果

問題 No.2620 Sieve of Coins
ユーザー suisensuisen
提出日時 2024-01-27 00:36:53
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 23 ms / 2,000 ms
コード長 1,916 bytes
コンパイル時間 755 ms
コンパイル使用メモリ 83,360 KB
実行使用メモリ 8,448 KB
最終ジャッジ日時 2024-09-28 09:19:43
合計ジャッジ時間 3,255 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 19 ms
8,316 KB
testcase_01 AC 19 ms
8,192 KB
testcase_02 AC 18 ms
8,320 KB
testcase_03 AC 22 ms
8,320 KB
testcase_04 AC 20 ms
8,320 KB
testcase_05 AC 17 ms
8,304 KB
testcase_06 AC 18 ms
8,192 KB
testcase_07 AC 18 ms
8,296 KB
testcase_08 AC 18 ms
8,320 KB
testcase_09 AC 17 ms
8,320 KB
testcase_10 AC 18 ms
8,192 KB
testcase_11 AC 18 ms
8,320 KB
testcase_12 AC 19 ms
8,320 KB
testcase_13 AC 18 ms
8,192 KB
testcase_14 AC 18 ms
8,320 KB
testcase_15 AC 18 ms
8,192 KB
testcase_16 AC 19 ms
8,192 KB
testcase_17 AC 18 ms
8,320 KB
testcase_18 AC 21 ms
8,192 KB
testcase_19 AC 22 ms
8,192 KB
testcase_20 AC 18 ms
8,192 KB
testcase_21 AC 21 ms
8,192 KB
testcase_22 AC 20 ms
8,320 KB
testcase_23 AC 17 ms
8,320 KB
testcase_24 AC 18 ms
8,192 KB
testcase_25 AC 18 ms
8,308 KB
testcase_26 AC 17 ms
8,192 KB
testcase_27 AC 20 ms
8,320 KB
testcase_28 AC 18 ms
8,320 KB
testcase_29 AC 20 ms
8,344 KB
testcase_30 AC 19 ms
8,192 KB
testcase_31 AC 21 ms
8,192 KB
testcase_32 AC 21 ms
8,320 KB
testcase_33 AC 18 ms
8,320 KB
testcase_34 AC 18 ms
8,320 KB
testcase_35 AC 18 ms
8,304 KB
testcase_36 AC 20 ms
8,320 KB
testcase_37 AC 19 ms
8,320 KB
testcase_38 AC 21 ms
8,320 KB
testcase_39 AC 21 ms
8,320 KB
testcase_40 AC 22 ms
8,308 KB
testcase_41 AC 20 ms
8,404 KB
testcase_42 AC 19 ms
8,192 KB
testcase_43 AC 22 ms
8,192 KB
testcase_44 AC 21 ms
8,320 KB
testcase_45 AC 18 ms
8,320 KB
testcase_46 AC 19 ms
8,320 KB
testcase_47 AC 20 ms
8,320 KB
testcase_48 AC 20 ms
8,320 KB
testcase_49 AC 20 ms
8,192 KB
testcase_50 AC 21 ms
8,192 KB
testcase_51 AC 23 ms
8,192 KB
testcase_52 AC 20 ms
8,320 KB
testcase_53 AC 21 ms
8,448 KB
testcase_54 AC 22 ms
8,192 KB
testcase_55 AC 18 ms
8,320 KB
testcase_56 AC 19 ms
8,192 KB
testcase_57 AC 20 ms
8,192 KB
権限があれば一括ダウンロードができます

ソースコード

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]) {
        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>

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