結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー AC2K
提出日時 2023-03-06 00:48:28
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 4,795 bytes
コンパイル時間 2,046 ms
コンパイル使用メモリ 196,324 KB
最終ジャッジ日時 2025-02-11 05:42:30
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 RE * 6
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:166:9: warning: #pragma once in main file
  166 | #pragma once
      |         ^~~~

ソースコード

diff # 

#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 u128 mod;
		static u128 R;
		static u128 n2;
	public:
		static u64 get_r() {
			u64 ret = mod;
			for (i64 i = 0; i < 5; ++i) ret *= 2 - mod * ret;
			return ret;
		}

		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 == (u128)1);
		}

	private:
		static u64 reduce(const u128& v) {
			u128 m = u128(u64(v) * u64(-R)) * mod;

			u64 t = (v + m) >> 64;

			return t;
		}
	public:
		static u64 get_mod() {
			return mod;
		}
	protected:
		u128 a;
	public:
		dynamic_modint(const i64& v = 0) :a(reduce((u128)v + mod)* n2) {}
		mint& operator=(const u64& v) {
			return (*this) = mint(v);
		}

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

			return (*this);
		}

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

		mint& operator*=(const mint& rhs) {
			a = reduce((u128)(a)*rhs.a);

			return (*this);
		}

		friend mint operator+(const mint& lhs, const mint& rhs) {
			return mint(lhs) += rhs;
		}
		friend mint operator-(const mint& lhs, const mint& rhs) {
			return mint(lhs) -= rhs;
		}
		friend mint operator*(const mint& lhs, const mint& rhs) {
			return mint(lhs) *= rhs;
		}


		mint& operator+=(const u64& rhs) {
			return (*this) += mint(rhs);
		}
		mint& operator-=(const u64& rhs) {
			return (*this) -= mint(rhs);
		}
		mint& operator*=(const u64& rhs) {
			return (*this) *= mint(rhs);
		}

		friend mint operator+(const mint& lhs, const u64& rhs) {
			return mint(lhs) += rhs;
		}
		friend mint operator+(const u64& lhs, const mint& rhs) {
			return mint(lhs) += rhs;
		}
		friend mint operator-(const mint& lhs, const u64& rhs) {
			return mint(lhs) -= rhs;
		}
		friend mint operator-(const u64& lhs, const mint& rhs) {
			return mint(lhs) += rhs;
		}
		friend mint operator*(const mint& lhs, const u64& rhs) {
			return mint(lhs) *= rhs;
		}
		friend mint operator*(const u64& lhs, const mint& rhs) {
			return mint(lhs) += rhs;
		}

		friend bool operator==(mint& lhs, mint& rhs) {
			if (lhs.a >= mod) {
				lhs.a -= mod;
			}

			if (rhs.a >= mod) {
				rhs.a -= mod;
			}


			return lhs.a == rhs.a;
		}

		u64 val() {
			assert(mod);
			u64 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);
		}
		mint& operator/=(const mint& rhs) {
			return (*this) *= rhs.inv();
		}
		friend mint operator/(const mint& lhs, const mint& rhs) {
			return mint(lhs) /= rhs;
		}
		friend mint operator/(const u64& lhs, const mint& rhs) {
			return mint(lhs) / rhs;
		}
		friend mint operator/(const mint& lhs, const u64& rhs) {
			return lhs / mint(rhs);
		}
	};
	typename dynamic_modint::u128 dynamic_modint::mod, dynamic_modint::n2, dynamic_modint::R;
};
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