結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー yosswi414
提出日時 2020-05-05 11:10:31
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,340 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 994 ms
コンパイル使用メモリ 95,280 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-18 17:51:26
合計ジャッジ時間 1,909 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <vector>
#include <string>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <algorithm>
#include <random>
#include <cassert>

using ll = long long;

template<class T>
T power(T x, T y, T p) {
	T res = 1;
	x = x % p;
	while (y) {
		if (y % 2 != 0)res = (res * x) % p;
		y /= 2;
		x = (x * x) % p;
	}
	return res;
}

ll uniformInteger(const ll& lower, const ll& upper) {
	assert(lower <= upper);
	std::random_device rnd;
	std::mt19937_64 mt(rnd());
	std::uniform_int_distribution<> rng(0, upper);
	ll rn = rng(mt);
	return rn + lower;
}

const int bound_mrpt = 2e1; // Pr = 1 / 4^bound_mrpt
bool MillerRabbinPrimalityTest(const ll& n, const int bound = bound_mrpt) {
	if (n<0) return false;
  if (n <= 1) return false;
	if (n == 2) return true;
	if (n % 2 == 0)return false;

	ll d = n - 1;
	int s = 0;
	for (;;) {
		if (d%2 != 0)break;
		d = d/2;
		++s;
	}
	for (int k = 0; k < bound; ++k) {
		ll a(uniformInteger(1, n - 1));
		ll ad(power(a, d, n));
		//std::cout << a << "\t" << ad << "\n";
		if (ad == 1) continue;
		for (int r = 1; r < s && ad != n - 1; ++r) {
			ad = (ad * ad) % n;
		}
		if (ad == n - 1)continue;
		else return false;
	}
	return true;
}


int main() {
	int n;
	std::cin>>n;
	while(n--){
	    ll p;
	    std::cin>>p;
	    std::cout<<p<<" "<<(MillerRabbinPrimalityTest(p)?1:0)<<std::endl;
	}
}
0