結果
問題 | No.8030 ミラー・ラビン素数判定法のテスト |
ユーザー |
|
提出日時 | 2022-11-26 10:58:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,488 bytes |
コンパイル時間 | 567 ms |
コンパイル使用メモリ | 70,660 KB |
最終ジャッジ日時 | 2025-02-09 01:18:28 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 5 WA * 5 |
ソースコード
#include <array>#include <cstdint>#include <iostream>#include <limits>using i32 = std::int32_t;using i64 = std::int64_t;using i128 = __int128_t;constexpr i64 mod_pow(i64 p, i64 q, i64 mod) {if (mod == 1) return 0;i64 res = 1;i64 b = p % mod;while (q) {if (q & 1) res = ((i128)res * b) % mod;b = ((i128)b * b) % mod;q >>= 1;}return res;}namespace impl {template <std::size_t N>constexpr bool miller_rabin(i64 n, std::array<i64, N> bases) {auto d = n - 1;while (d % 2 == 0) d >>= 1;for (auto b : bases) {if (n <= b) break;auto t = d;auto y = mod_pow(b, t, n);while (t != n - 1 && y != 1 && y != n - 1) {y = y * y % n;t <<= 1;}if (y != n - 1 && t % 2 == 0) {return false;}}return true;}} // namespace implconstexpr bool is_prime(i64 n) {if (not(n & 1)) return n == 2;if (n <= 1) return false;if (n <= std::numeric_limits<int>::max()) {std::array<i64, 3> bases = {2, 7, 61};return impl::miller_rabin(n, bases);} else {std::array<i64, 7> bases = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};return impl::miller_rabin(n, bases);}}int main() {i32 n;std::cin >> n;for (i32 i = 0; i < n; ++i) {i64 x;std::cin >> x;std::cout << x << (is_prime(x) ? " 1" : " 0") << std::endl;}}