結果
問題 | No.8030 ミラー・ラビン素数判定法のテスト |
ユーザー | AC2K |
提出日時 | 2023-02-15 17:47:42 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 955 ms / 9,973 ms |
コード長 | 2,079 bytes |
コンパイル時間 | 2,053 ms |
コンパイル使用メモリ | 203,568 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-18 02:14:24 |
合計ジャッジ時間 | 5,731 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,944 KB |
testcase_04 | AC | 518 ms
6,944 KB |
testcase_05 | AC | 503 ms
6,944 KB |
testcase_06 | AC | 186 ms
6,940 KB |
testcase_07 | AC | 185 ms
6,944 KB |
testcase_08 | AC | 185 ms
6,944 KB |
testcase_09 | AC | 955 ms
6,940 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; #define rep(i, N) for(int i=0;i<(N);i++) #define all(x) (x).begin(),(x).end() #define popcount(x) __builtin_popcount(x) using ll = long long; //using i128=__int128_t; using ld = long double; using graph = vector<vector<int>>; using P = pair<int, int>; const int inf = 1e9; const ll infl = 1e18; const ld eps = 1e-6; const long double pi = acos(-1); const ll MOD = 1e9 + 7; const ll MOD2 = 998244353; const int dx[4] = { 1,0,-1,0 }; const int dy[4] = { 0,1,0,-1 }; template<class T>inline void chmax(T&x,T y){if(x<y)x=y;} template<class T>inline void chmin(T&x,T y){if(x>y)x=y;} class MillerRabin { using i128 = __int128_t; const vector<ll> bases = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 }; //intだと、2,7,61で十分 i128 mod_pow(i128 base, i128 exp, ll mod) { i128 ans = 1; base %= mod; while (exp) { if (exp & 1) { ans *= base; ans %= mod; } base *= base; base %= mod; exp >>= 1; } return ans; } public: bool is_prime(ll n) { if (n < 2) { return false; } ll d = n - 1; ll q = 0; while ((d & 1) == 0) { d >>= 1; q++; } for (ll a : bases) { if (a == n) { return true; } if (mod_pow(a, d, n) != 1) { bool flag = true; for (ll r = 0; r < q; r++) { ll pow = mod_pow(a, d * (1ll << r), n); if (pow == n - 1) { flag = false; break; } } if (flag) { return false; } } } return true; } }rho; int main() { int n; cin >> n; while(n--){ ll x; cin >> x; cout << x << ' '; if(rho.is_prime(x))cout << 1 << '\n'; else cout << 0 << '\n'; } }