結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー wasd314
提出日時 2025-01-12 01:43:49
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 281 ms / 9,973 ms
コード長 1,863 bytes
コンパイル時間 1,732 ms
コンパイル使用メモリ 102,612 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2025-01-12 01:43:53
合計ジャッジ時間 2,752 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <bit>
#include <iostream>
#include <vector>

using lint = long long;
bool is_prime(lint n)
{
    using lint2 = __int128_t;
    if (n < 2) return false;
    for (lint p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
        if (n == p) return true;
        if (n % p == 0) return false;
    }
    if (n < 41 * 41) return true;
    auto mul_mod = [&](lint x, lint y) -> lint {
        return lint2(x) * y % n;
    };
    auto pow_mod = [&](lint x, lint e) {
        lint p = 1;
        while (e) {
            if (e & 1) p = mul_mod(p, x);
            x = mul_mod(x, x);
            e >>= 1;
        }
        return p;
    };
    auto test_miller_rabin = [&](const std::vector<lint> &bases) {
        int e = std::countr_zero((unsigned long long)(n - 1));
        lint o = n >> e;
        for (lint b : bases) {
            lint x = pow_mod(b, o);
            if (x == 1) continue;
            for (int ei = 0; ei < e; ++ei) {
                lint y = mul_mod(x, x);
                if (y == 1) {
                    if (x == n - 1) break;
                    return false;
                }
                x = y;
                if (ei == e - 1) return false;
            }
        }
        return true;
    };
    if (n < 2047) return test_miller_rabin({2});
    if (n < 9080191) return test_miller_rabin({31, 73});
    if (n < 4759123141) return test_miller_rabin({2, 7, 61});
    if (n < 1122004669633) return test_miller_rabin({2, 13, 23, 1662803});
    if (n < 3770579582154547) return test_miller_rabin({2, 880937, 2570940, 610386380, 4130785767});
    return test_miller_rabin({2, 325, 9375, 28178, 450775, 9780504, 1795265022});
}

int main()
{
    using namespace std;
    int q;
    cin >> q;
    for (int _ = 0; _ < q; ++_) {
        lint n;
        cin >> n;
        cout << n << ' ' << is_prime(n) << "\n";
    }
}
0