結果
問題 | No.3030 ミラー・ラビン素数判定法のテスト |
ユーザー | hitonanode |
提出日時 | 2020-04-19 04:40:52 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,847 bytes |
コンパイル時間 | 676 ms |
コンパイル使用メモリ | 76,152 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-18 17:49:16 |
合計ジャッジ時間 | 1,972 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | WA | - |
testcase_05 | AC | 147 ms
5,248 KB |
testcase_06 | AC | 70 ms
5,248 KB |
testcase_07 | AC | 72 ms
5,248 KB |
testcase_08 | AC | 71 ms
5,248 KB |
testcase_09 | AC | 255 ms
5,248 KB |
ソースコード
#include <array> #include <algorithm> #include <cassert> #include <vector> namespace SPRP { // <http://miller-rabin.appspot.com/> const std::vector<std::vector<__int128>> bases{ {126401071349994536}, // <= 291831 {336781006125, 9639812373923155}, // <= 1050535501 (1e9) {2, 2570940, 211991001, 3749873356}, // <= 47636622961201 (4e13) {2, 325, 9375, 28178, 450775, 9780504, 1795265022} // <= 1e64 }; inline int get_id(long long n) { if (n <= 291831) return 0; else if (n <= 1050535501) return 1; else if (n <= 47636622961201) return 2; else return 3; } } // namespace SPRP // Miller-Rabin primality test // <https://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%A9%E3%83%BC%E2%80%93%E3%83%A9%E3%83%93%E3%83%B3%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95> // Complexity: O(lg n) per query struct { long long modpow(__int128 x, __int128 n, long long mod) noexcept { __int128 ret = 1; for (x %= mod; n; x = x * x % mod, n >>= 1) ret = (n & 1) ? ret * x % mod : ret; return ret; } bool operator()(long long n) noexcept { if (n < 2) return false; if (n % 2 == 0) return n == 2; int s = __builtin_ctzll(n - 1); for (__int128 a : SPRP::bases[SPRP::get_id(n)]) { a = modpow(a, (n - 1) >> s, n); bool may_composite = true; if (!a) return true; if (a == 1) continue; for (int r = s; r--; a = a * a % n) if (a == n - 1) may_composite = false; if (may_composite) return false; } return true; } } is_prime; #include <iostream> int main() { int Q; std::cin >> Q; while (Q--) { long long n; std::cin >> n; std::cout << n << ' ' << is_prime(n) << '\n'; } }