結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー AC2KAC2K
提出日時 2023-03-06 00:33:40
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 3,753 bytes
コンパイル時間 2,226 ms
コンパイル使用メモリ 201,468 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-18 01:43:46
合計ジャッジ時間 3,382 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
main.cpp:104:9: warning: #pragma once in main file
  104 | #pragma once
      |         ^~~~

ソースコード

diff # 

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

namespace modint {
	class dynamic_modint {
		using i64 = int64_t;
		using u64 = uint64_t;
		using u128 = __uint128_t;
		using i128 = __int128_t;
		using mint = modint::dynamic_modint;
		static u64 mod;
		static u64 R;
		static u64 n2;

		static u64 get_r() {
			u64 ret = mod;
			for (i64 i = 0; i < 5; ++i) ret *= 2 - mod * ret;
			return ret;
		}
	public:
		static void set_mod(u64 m) {
			assert(m < (1LL << 62));
			assert((m & 1) == 1);
			mod = m;
			n2 = -u128(m) % m;
			R = get_r();
			assert(R * mod == 1);
		}

		static u64 get_mod() {
			return mod;
		}
	protected:
		u128 a;
	public:
		dynamic_modint(const i64& v = 0) :a(reduce((u128)v + mod)* n2) {}
    private:
		static u64 reduce(const u128& b) {
            return (b + u128(u64(b) * u64(-R)) * mod) >> 64;
        }

    public:
		mint& operator+=(const mint& b) {
			if (i64(a += b.a - 2 * mod) < 0) a += 2 * mod;
			return *this;
		}

		mint& operator-=(const mint& b) {
			if (i64(a -= b.a) < 0) a += 2 * mod;
			return *this;
		}

		mint& operator*=(const mint& b) {
			a = reduce(u128(a) * b.a);
			return (*this);
		}

		mint& operator/=(const mint& b) {
			*this *= b.inv();
			return *this;
		}
		mint operator+(const mint& b) const { return mint(*this) += b; }
		mint operator-(const mint& b) const { return mint(*this) -= b; }
		mint operator*(const mint& b) const { return mint(*this) *= b; }
		mint operator/(const mint& b) const { return mint(*this) /= b; }
		bool operator==(const mint& b) const {
			return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a);
		}
		bool operator!=(const mint& b) const {
			return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a);
		}
		mint operator-() const { return mint() - mint(*this); }

		u64 val() {
			assert(mod);
			u128 v = reduce(a);

			if (v >= mod) {
				v -= mod;
			}

			return v;
		}
		mint pow(u128 e) const {
			mint pw(1), base((*this));
			while (e) {
				if (e & 1) {
					pw *= base;
				}
				base *= base;
				e >>= 1;
			}
			return pw;
		}

		mint inv() const {
			return pow(mod - 2);
		}
	};
    typename dynamic_modint::u64 dynamic_modint::mod, dynamic_modint::R, dynamic_modint::n2;
};
using modint::dynamic_modint;
#pragma once
//#include"math/mod_pow.hpp"
namespace prime {
	namespace miller {
		using i128 = __int128_t;
		using u128 = __uint128_t;
		using u64 = __uint64_t;
		using mint = modint::dynamic_modint;
		bool miller_rabin(u64 n, const u64 bases[], int siz) {
			if (mint::get_mod() != n) {
				mint::set_mod(n);
			}



			u64 d = n - 1;
			u64 q = __builtin_ctz(d);
			d >>= q;

			for (int i = 0; i < siz; i++) {
				u64 a = bases[i];
				if (a == n) {
					return true;
				}
				else if (n % a == 0) {
					return false;
				}
				if (mint(a).pow(d).val() != 1) {
					bool flag = true;
					for (u64 r = 0; r < q; r++) {
						mint pow = mint(a).pow(d * (1ll << r));
						if (pow.val() == n - 1) {
							flag = false;
							break;
						}
					}

					if (flag) {
						return false;
					}
				}
			}
			return true;
		}


		bool is_prime(u64 n) {
			static constexpr u64 bases_int[3] = { 2, 7, 61 };  // intだと、2,7,61で十分
			static constexpr u64 bases_ll[7] = { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 };
			if (n < 2) {
				return false;
			}
			else if (n == 2) {
				return true;
			}
			else if (~n & 1) {
				return false;
			}

			if (n < (1ul << 31)) {
				return miller_rabin(n, bases_int, 3);
			}
			else {
				return miller_rabin(n, bases_ll, 7);
			}
		}
	};
};
using prime::miller::is_prime;
///@brief fast prime check(MillerRabinの素数判定)
int main() {
	int n;
	cin >> n;
	while (n--) {
		long long x;
		cin >> x;
		cout << x << ' ' << is_prime(x) << '\n';
	}
}
0