結果
問題 | No.8030 ミラー・ラビン素数判定法のテスト |
ユーザー | kusano |
提出日時 | 2023-01-08 21:24:16 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,496 bytes |
コンパイル時間 | 834 ms |
コンパイル使用メモリ | 65,220 KB |
実行使用メモリ | 13,640 KB |
最終ジャッジ日時 | 2024-12-16 01:06:39 |
合計ジャッジ時間 | 40,450 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
8,576 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 3 ms
5,248 KB |
testcase_03 | AC | 4 ms
5,248 KB |
testcase_04 | AC | 9,352 ms
5,248 KB |
testcase_05 | AC | 9,462 ms
5,248 KB |
testcase_06 | AC | 3,062 ms
5,248 KB |
testcase_07 | AC | 3,051 ms
5,248 KB |
testcase_08 | AC | 3,043 ms
5,248 KB |
testcase_09 | TLE | - |
ソースコード
long long mulmod(long long a, long long b, long long m) { unsigned long long a_ = (unsigned long long)a; unsigned long long b_ = (unsigned long long)b; unsigned long long m_ = (unsigned long long)m; unsigned long long r = 0; for (; b_>0; b_>>=1, a_=(a_+a_)%m_) if (b_&1) r = (r+a_)%m_; return (long long)r; } long long powmod(long long a, long long b, long long m) { long long r = 1; for (; b>0; b>>=1, a=mulmod(a, a, m)) if (b&1) r = mulmod(r, a, m); return r; } bool is_prime(long long n) { if (n==1) return false; if (n==2) return true; if (n%2==0) return false; long long d = n-1; long long s = 0; while (d%2==0) { d /= 2; s++; } // https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Testing_against_small_sets_of_bases long long A[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}; for (long long a: A) { if (a>=n) break; bool composite = powmod(a, d, n)!=1; long long t = d; for (int i=0; i<s && composite; i++, t*=2) if (powmod(a, t, n)==n-1) composite = false; if (composite) return false; } return true; } #include <iostream> using namespace std; int main() { int n; cin>>n; for (int i=0; i<n; i++) { long long x; cin>>x; cout<<x<<" "<<is_prime(x)<<endl; } }