結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー AC2KAC2K
提出日時 2023-03-06 01:01:35
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,765 bytes
コンパイル時間 2,238 ms
コンパイル使用メモリ 201,624 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-18 01:47:30
合計ジャッジ時間 3,056 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:149:9: warning: #pragma once in main file
  149 | #pragma once
      |         ^~~~

ソースコード

diff # 

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

namespace modint {
	class dynamic_modint {
		using mint = dynamic_modint;
		using i64 = __int64_t;
		using u64 = __uint64_t;
		using u128 = __uint128_t;
		using i128 = __int128_t;
		static u128 mod;
		static u128 r;
		static u128 n2;
	private:
		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 < ((u128)1 << 64));
			assert(m & 1);
			mod = m;
			n2 = -u128(m) % m;
			r = get_r();
		}
	private:
		u64 a;
	public:
		dynamic_modint() : a(0) {}
		dynamic_modint(const i64& b) : a(reduce((u128(b) + 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);
		}

		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; 
		}
		friend mint operator/(const mint&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 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 u64& lhs, const mint& rhs) {
			return mint(lhs) / rhs;
		}
		friend mint operator/(const mint& lhs, const u64& rhs) {
			return lhs / mint(rhs);
		}

		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); }

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

		friend ostream& operator<<(ostream& os, const mint& b) {
			return os << b.val();
		}

		friend istream& operator>>(istream& is, mint& b) {
			int64_t t;
			is >> t;
			b = dynamic_modint(t);
			return (is);
		}

		mint inv() const { return pow(mod - 2); }

		u64 val() const {
			u64 ret = reduce(a);
			return ret >= mod ? ret - mod : ret;
		}

		static u64 get_mod() { return mod; }
	};
	typename dynamic_modint::u128 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