結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー ningenMe
提出日時 2020-09-05 16:24:08
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 937 bytes
コンパイル時間 2,005 ms
コンパイル使用メモリ 193,188 KB
最終ジャッジ日時 2025-01-14 07:12:58
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9 WA * 1
権限があれば一括ダウンロードができます

ソースコード

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