結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー nonamaenonamae
提出日時 2022-07-19 18:03:50
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,100 bytes
コンパイル時間 2,042 ms
コンパイル使用メモリ 201,724 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-01 21:25:38
合計ジャッジ時間 3,409 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
using u8 = std::uint8_t; using u16 = std::uint16_t; using u32 = std::uint32_t; using u64 = std::uint64_t; using u128 = __uint128_t;
bool mr32(u32 n, u32 a) { if (!(a %= n)) return 1; u8 r = __builtin_ctz(n - 1); u32 d = n >> r, p = 1; for (; d; d >>= 1, a = u64(a) * a % n) { if (d & 1) p = u64(p) * a % n; } if (p == 1) return 1; while (p != n - 1 && --r) { p = u64(p) * p % n; } return p == n - 1; }
bool mr64(u64 n, u64 a) { if (!(a %= n)) return 1; u8 r = __builtin_ctzll(n - 1); u64 d = n >> r, p = 1; for (; d; d >>= 1, a = u128(a) * a % n) { if (d & 1) p = u128(p) * a % n; } if (p == 1) return 1; while (p != n - 1 && --r) { p = u128(p) * p % n; } return p == n - 1; }
bool dmr32(u32 n) { if (n < 49141) return mr32(n, 921211727); if (n < 316349281) return mr32(n, 11000544) && mr32(n, 31481107); return mr32(n, 2) && mr32(n, 7) && mr32(n, 61); }
bool dmr64(u64 n) { if (n <= 0xffffffff) return dmr32(n); if (n < 350269456337) mr64(n, 4230279247111683200) && mr64(n, 14694767155120705706u) && mr64(n, 16641139526367750375u); if (n < 55245642489451) mr64(n, 2) && mr64(n, 141889084524735) && mr64(n, 1199124725622454117) && mr64(n, 11096072698276303650u); if (n < 7999252175582851) mr64(n, 2) && mr64(n, 4130806001517) && mr64(n, 149795463772692060) && mr64(n, 186635894390467037) && mr64(n, 3967304179347715805); if (n < 585226005592931977) mr64(n, 2) && mr64(n, 123635709730000) && mr64(n, 9233062284813009) && mr64(n, 43835965440333360) && mr64(n, 761179012939631437) && mr64(n, 1263739024124850375); return mr64(n, 2) && mr64(n, 325) && mr64(n, 9375) && mr64(n, 28178) && mr64(n, 450775) && mr64(n, 9780504) && mr64(n, 1795265022); }
bool is_prime(u64 n) {
    if (n <= 1) return false;
    if (n == 2 || n == 3 || n == 5 || n == 7) return true;
    if (!(n & 1)) return false;
    if (n % 3 == 0 || n % 5 == 0 || n % 7 == 0 ) return false;
    if (n < 121) return n > 1;
    return dmr64(n);
}
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        unsigned long long int x;
        scanf("%llu", &x);
        printf("%llu %d\n", x, dmr64(x));
    }
}
0