結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー nonamaenonamae
提出日時 2022-07-14 17:12:30
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 3,026 bytes
コンパイル時間 645 ms
コンパイル使用メモリ 35,016 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-26 00:53:20
合計ジャッジ時間 1,985 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,812 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdint>
#include <cassert>
#include <cstdio>
#include <initializer_list>

struct Dyn_Mont_mint64 {
    
    using i64 = std::int64_t;
    using u64 = std::uint64_t;
    using u128 = __uint128_t;

    // r * m === -1 (mod 1 << 64)
    // n2 === 1 <<< 128 (mod m)
    inline static u64 m, r, n2;
    static void set_mod(u64 m) {
        assert(m < (1ull << 62));
        assert((m & 1) == 1);
        Dyn_Mont_mint64::m = m;
        n2 = -u128(m) % m;
        r = m;
        for (int _ = 0; _ < 5; ++_) r *= 2 - m * r;
        r = -r;
        assert(r * m == -1ull);
    }
    static u64 reduce(u128 b) {
        return (b + u128(u64(b) * r) * m) >> 64;
    }
    
    u64 x;

    Dyn_Mont_mint64() : x(0) { }
    Dyn_Mont_mint64(u64 x) : x(reduce(u128(x) * n2)) { }
    u64 val() const {
        u64 y = reduce(x);
        return y >= m ? y - m : y;
    }
    Dyn_Mont_mint64 &operator+=(Dyn_Mont_mint64 y) {
        x += y.x - (m << 1);
        x = (i64(x) < 0 ? x + (m << 1) : x);
        return *this;
    }
    Dyn_Mont_mint64 &operator-=(Dyn_Mont_mint64 y) {
        x -= y.x;
        x = (i64(x) < 0 ? x + (m << 1) : x);
        return *this;
    }
    Dyn_Mont_mint64 &operator*=(Dyn_Mont_mint64 y) {
        x = reduce(u128(x) * y.x);
        return *this;
    }
    Dyn_Mont_mint64 operator+(Dyn_Mont_mint64 y) const { return Dyn_Mont_mint64(*this) += y; }
    Dyn_Mont_mint64 operator-(Dyn_Mont_mint64 y) const { return Dyn_Mont_mint64(*this) -= y; }
    Dyn_Mont_mint64 operator*(Dyn_Mont_mint64 y) const { return Dyn_Mont_mint64(*this) *= y; }
    bool operator==(Dyn_Mont_mint64 y) const {
        return (x >= m ? x - m : x) == (y.x >= m ? y.x - m : y.x);
    }
    bool operator!=(Dyn_Mont_mint64 y) const {
        return not operator==(y);
    }
    Dyn_Mont_mint64 pow(u64 n) const {
        Dyn_Mont_mint64 y = 1, z = *this;
        for ( ; n; n >>= 1, z *= z) if (n & 1) y *= z;
        return y;
    }
};


using m64 = Dyn_Mont_mint64;

bool is_prime(const std::uint64_t x) {
    if (x == 2 or x == 3 or x == 5 or x == 7) return true;
    if (x % 2 == 0 or x % 3 == 0 or x % 5 == 0 or x % 7 == 0) return false;
    if (x < 121) return x > 1;
    const std::uint64_t d = (x - 1) >> __builtin_ctzll(x - 1);
    m64::set_mod(x);
    const m64 one{1}, rev{x - 1};
    auto ok = [&](std::uint64_t a) {
        auto y = m64(a).pow(d);
        std::uint64_t t = d;
        while (y != one and y != rev and t != x-1) y *= y, t <<= 1;
        if (y != rev and t % 2 == 0) return false;
        return true;
    };
    if (x < (1ull << 32)) {
        for (std::uint64_t a : { 2, 7, 61 }) if (not ok(a)) return false;
    } else {
        for (std::uint64_t a : { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 }) {
            if (x <= a) return true;
            if (not ok(a)) return false;
        }
    }
    return true;
}

int main() {
    std::uint64_t n; scanf("%lu", &n);
    while (n--) {
        std::uint64_t x; scanf("%lu", &x);
        printf("%lu %d\n", x, (is_prime(x) ? 1 : 0));
    }
}
0