結果
問題 | No.3030 ミラー・ラビン素数判定法のテスト |
ユーザー | Haar |
提出日時 | 2020-03-23 05:26:43 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 454 ms / 9,973 ms |
コード長 | 2,002 bytes |
コンパイル時間 | 2,268 ms |
コンパイル使用メモリ | 206,540 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-04-28 09:29:08 |
合計ジャッジ時間 | 4,063 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 244 ms
5,376 KB |
testcase_05 | AC | 239 ms
5,376 KB |
testcase_06 | AC | 72 ms
5,376 KB |
testcase_07 | AC | 70 ms
5,376 KB |
testcase_08 | AC | 70 ms
5,376 KB |
testcase_09 | AC | 454 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> #ifdef DEBUG #include <boost/multiprecision/cpp_int.hpp> using int128_t = boost::multiprecision::int128_t; #else using int128_t = __int128_t; #endif class MillerRabin{ static inline int128_t power(int128_t a, int128_t b, int128_t p){ int128_t ret = 1; while(b > 0){ if(b & 1) ret = ret * a % p; a = a * a % p; b >>= 1; } return ret; } static inline bool is_composite(uint64_t a, uint64_t p){ int s = 0; uint64_t d = p-1; while((d & 1) == 0){ s += 1; d >>= 1; } int128_t x = power(a, d, p); if(x == 1) return false; for(int i = 0; i < s; ++i){ if(x == p-1) return false; x = x * x % p; } return true; } public: static inline bool is_prime(uint64_t n){ if(n <= 1) return false; if(n == 2) return true; if(n % 2 == 0) return false; if(n < 4759123141){ if(2 < n and is_composite(2, n)) return false; if(7 < n and is_composite(7, n)) return false; if(61 < n and is_composite(61, n)) return false; return true; } if(2 < n and is_composite(2, n)) return false; if(3 < n and is_composite(3, n)) return false; if(5 < n and is_composite(5, n)) return false; if(7 < n and is_composite(7, n)) return false; if(11 < n and is_composite(11, n)) return false; if(13 < n and is_composite(13, n)) return false; if(17 < n and is_composite(17, n)) return false; if(19 < n and is_composite(19, n)) return false; if(23 < n and is_composite(23, n)) return false; if(29 < n and is_composite(29, n)) return false; if(31 < n and is_composite(31, n)) return false; if(37 < n and is_composite(37, n)) return false; return true; } }; int main(){ std::cin.tie(0); std::ios::sync_with_stdio(false); int N; std::cin >> N; for(int i = 0; i < N; ++i){ int64_t x; std::cin >> x; std::cout << x << " " << MillerRabin::is_prime(x) << std::endl; } return 0; }