結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー ningenMeningenMe
提出日時 2020-09-05 16:22:54
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 936 bytes
コンパイル時間 2,055 ms
コンパイル使用メモリ 200,560 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-29 14:14:06
合計ジャッジ時間 3,358 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 138 ms
5,376 KB
testcase_05 AC 133 ms
5,376 KB
testcase_06 AC 55 ms
5,376 KB
testcase_07 AC 54 ms
5,376 KB
testcase_08 AC 54 ms
5,376 KB
testcase_09 AC 242 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

class Prime{
	using int128 = __int128_t;
	using int64  = long long;
	long long pow(long long x, long long n, long long mod) {		long long res = 1;
		for (x %= mod; n > 0; n >>= 1, x=(int128(x)*x)%mod) if (n & 1) res = (int128(res)*x)%mod;
		return res;
	}
public:
	int miller_rabin(const int64 n) {
        if(n == 2) return 1;
        if(n < 2 || n%2 == 0) return 0;
		int64 m = n - 1;
		for (;!(m&1);m>>=1);
		for (int64 a: {2,325,9375,28178,450775,9780504,1795265022}) {
			if(a>=n) break;
            int64 x=m,r=pow(a,x,n);
            for(;x != n-1 && r != 1 && r != n-1;x <<= 1) r = (int128(r)*r)%n;
            if(r!=n-1 && x%2==0) return 0;
		}
		return 1;
	}
};

int main() {
	cin.tie(0);ios::sync_with_stdio(false);
    long long N; cin >> N;
	Prime P;
    for(int i = 0; i < N; ++i) {
		long long A; cin >> A;
		cout << A << " " << P.miller_rabin(A) << "\n";
	}
    return 0;
}
0