結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー nonamae
提出日時 2022-07-19 17:55:37
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,839 bytes
コンパイル時間 2,550 ms
コンパイル使用メモリ 193,272 KB
最終ジャッジ日時 2025-01-30 11:09:17
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9 WA * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:8:17: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    8 |     int T; scanf("%d", &T);
      |            ~~~~~^~~~~~~~~~
main.cpp:11:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   11 |         scanf("%llu", &x);
      |         ~~~~~^~~~~~~~~~~~

ソースコード

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); }
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