結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー ningenMeningenMe
提出日時 2020-09-05 04:15:03
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 825 bytes
コンパイル時間 1,386 ms
コンパイル使用メモリ 160,776 KB
最終ジャッジ日時 2024-11-14 23:49:48
合計ジャッジ時間 1,755 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、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>':
main.cpp:13:15:   required from 'int MillerRabin(T, int) [with T = __int128]'
main.cpp:27:55:   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

ソースコード

diff # 

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

// N <= 1e9 -> long long
// N > 1e9  -> int128
template<class T> int MillerRabin(const T N, int challenge = 10) {
	if (N <= 1) return 0;
	if (N == 2) return 1;
	T M = N - 1,cnt = 0;
	for (; M % 2 == 0; M /= 2,cnt++);
	mt19937 mt(time(NULL));
	for (int i = 0; i < 10; ++i) {
        T a = uniform_int_distribution<T>(2, N - 1)(mt), r = 1;
		for (T K = M; K > 0; K >>= 1, (a *= a) %= N) if (K & 1) (r *= a) %= N;
		if (r == 1) continue;
		for (int j = 1; j < cnt && r != N - 1; j++) (r *= r) %= N;
		if (r != N - 1) return 0;
	}
	return 1;
}

int main() {
    long long N; cin >> N;
    vector<long long> A(N);
    for(int i = 0; i < N; ++i) cin >> A[i];
    for(int i = 0; i < N; ++i) {
        cout << A[i] << " " << MillerRabin<__int128_t>(A[i]) << endl;
    }
    return 0;
}
0