結果
問題 | No.3030 ミラー・ラビン素数判定法のテスト |
ユーザー | kappybar |
提出日時 | 2020-04-29 16:16:47 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,202 bytes |
コンパイル時間 | 1,504 ms |
コンパイル使用メモリ | 159,836 KB |
最終ジャッジ日時 | 2024-11-14 22:28:28 |
合計ジャッジ時間 | 1,933 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/stl_algo.h:65, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/algorithm:61, from /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/x86_64-pc-linux-gnu/bits/stdc++.h:65, from main.cpp:1: /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/uniform_int_dist.h: In instantiation of 'class std::uniform_int_distribution<__int128 unsigned>': main.cpp:33:48: required from here /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/uniform_int_dist.h:79:49: error: static assertion failed: template argument must be an integral type 79 | static_assert(std::is_integral<_IntType>::value, | ^~~~~ /home/linuxbrew/.linuxbrew/Cellar/gcc@12/12.3.0/include/c++/12/bits/uniform_int_dist.h:79:49: note: 'std::integral_constant<bool, false>::value' evaluates to false
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<n;i++) using namespace std; using ll = long long ; using P = pair<int,int> ; using pll = pair<ll,ll>; const ll INF = 1e18; const int MOD = 1000000007; using u128 = __uint128_t; u128 modpow(u128 x, u128 n,u128 mod) { u128 ret = 1; while (n > 0) { if (n & 1) ret = (ret * x) % mod; x = (x * x) % mod; n >>= 1; } return ret; } bool Miller_Rabin(u128 x){ if(x == 0) return false; if(x == 1) return false; if(x == 2) return true; if(x%2 == 0) return false; u128 d = x - 1; while(d%2 == 0) d /= 2; random_device rand; mt19937 mt(rand()); uniform_int_distribution<u128> random_maker(1,x-1); for(int i = 0;i < 100; ++i){ u128 p = random_maker(mt); u128 a = modpow(p,d,x); u128 s = d; while(s != x-1 && a != 1 && a != x-1){ a = (a * a)%x; s <<= 1; } if(a != x-1 && s%2 == 0) return false; } return true; } int main(){ int n; cin >> n; while(n--){ ll x; cin >> x; cout << x << " " ; cout << (Miller_Rabin(x) ? 1 : 0) << endl; } return 0; }