結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー AC2KAC2K
提出日時 2023-03-31 12:02:44
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 562 ms / 9,973 ms
コード長 6,042 bytes
コンパイル時間 3,028 ms
コンパイル使用メモリ 247,984 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-22 16:56:24
合計ジャッジ時間 5,476 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 324 ms
6,940 KB
testcase_05 AC 327 ms
6,940 KB
testcase_06 AC 168 ms
6,944 KB
testcase_07 AC 168 ms
6,940 KB
testcase_08 AC 169 ms
6,940 KB
testcase_09 AC 562 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#line 2 "math/barrett.hpp"
namespace internal {
	///@brief barrett reduction
	class barrett {
		using u32 = uint32_t;
		using u64 = uint64_t;

		u32 m;
		u64 im;
	public:
		explicit barrett() = default;
		constexpr explicit barrett(const u32& m_) :m(m_), im((u64)(-1) / m_ + 1) {}

		u32 get_mod() const { return m; }
		u32 mul(u32 a, u32 b) {
			if (a == 0 || b == 0) {
				return 0;
			}
			u64 z = a;
			z *= b;
#ifdef _MSC_VER
			u64 x;

			_umul128(z, im, &x);
#else
			u64 x = (u64)(((__uint128_t)(z)*im) >> 64);
#endif

			u32 v = (u32)(z - x * m);

			if (v >= m)v += m;
			return v;
		}
	};
}
#line 3 "math/dynamic_modint.hpp"
class dynamic_modint32 {
	using u32 = uint32_t;
	using u64 = uint64_t;

	using i32 = int32_t;
	using i64 = int64_t;
	using br = internal::barrett;

	static br brt;
	static u32 mod;
	u32 v;	//value
public:
	static void set_mod(const u32& mod_) {
		brt = br(mod_);
		mod = mod_;
	}
private:
	u32 normalize(const i64& x) const {
		i32 m = x % mod;
		if (m < 0) {
			m += mod;
		}
		return m;
	}
public:
	dynamic_modint32() :v(0) { assert(mod); }	//modが決定済みである必要がある
	dynamic_modint32(const i64& v_) :v(normalize(v_)) { assert(mod); }

	u32 val() const { return v; }
	static u32 get_mod() { return mod; }
	using mint = dynamic_modint32;

	//operators
	mint& operator=(const i64& r) {
		v = normalize(r);
		return (*this);
	}
	mint& operator+=(const mint& r) {
		v += r.v;
		if (v >= mod) {
			v -= mod;
		}
		return (*this);
	}
	mint& operator-=(const mint& r) {
		v += mod - r.v;
		if (v >= mod) {
			v -= mod;
		}

		return (*this);
	}
	mint& operator*=(const mint& r) {
		v = brt.mul(v, r.v);
		return (*this);
	}

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



	mint& operator+= (const i64& r) { return (*this) += mint(r); }
	mint& operator-= (const i64& r) { return (*this) -= mint(r); }
	mint& operator*= (const i64& r) { return (*this) *= mint(r); }

	friend mint operator+(const i64& l, const mint& r) { return mint(l) += r; }
	friend mint operator+(const mint& l, const i64& r) { return mint(l) += r; }
	friend mint operator-(const i64& l, const mint& r) { return mint(l) -= r; }
	friend mint operator-(const mint& l, const i64& r) { return mint(l) -= r; }
	friend mint operator*(const i64& l, const mint& r) { return mint(l) *= r; }
	friend mint operator*(const mint& l, const i64& r) { return mint(l) += r; }


	friend ostream& operator<<(ostream& os, const mint& mt) {
		os << mt.val();
		return os;
	}
	friend istream& operator>>(istream& is, mint& mt) {
		i64 v_;
		is >> v_;
		mt = v_;
		return is;
	}
	mint pow(u64 e) const {
		mint res(1), base(*this);

		while (e) {
			if (e & 1) {
				res *= base;
			}
			e >>= 1;
			base *= base;
		}
		return res;
	}
	mint inv() const {
		return pow(mod - 2);
	}

	mint& operator/=(const mint& r) { return (*this) *= r.inv(); }
	mint operator/(const mint& r) const { return mint(*this) *= r.inv(); }
	mint& operator/=(const i64& r) { return (*this) /= mint(r); }
	friend mint operator/(const mint& l, const i64& r) { return mint(l) /= r; }
	friend mint operator/(const i64& l, const mint& r) { return mint(l) /= r; }
};
typename dynamic_modint32::u32 dynamic_modint32::mod;
typename dynamic_modint32::br dynamic_modint32::brt;

///@brief dynamic modint(動的modint)
///@docs docs/math/dynamic_modint.md

template <class T, class U = T>
constexpr inline U mod_pow(T base, T exp, T mod) {
	T ans = 1;
	base %= mod;
	while (exp > 0) {
		if (exp & 1) {
			ans *= base;
			ans %= mod;
		}
		base *= base;
		base %= mod;
		exp >>= 1;
	}
	return ans;
}


namespace prime {
    namespace miller {
        using i128 = __int128_t;
        using u128 = __uint128_t;
        using u64 = uint64_t;
		using u32 = uint32_t;

		constexpr bool miller_rabin_int(u32 n) {
			constexpr int bases_int[] = { 2, 7, 61 };
			constexpr int siz = 3;
			if (n < 2) {
				return false;
			}
			else if (n == 2) {
				return true;
			}
			if (~n & 1) {
				return false;
			}



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


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

					if (flag) {
						return false;
					}
				}
			}
			return true;
		}
		constexpr bool miller_rabin_long(u64 n) {
			constexpr u64 bases_long[] = { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 };
			constexpr int siz = 7;

			if (n < 2) {
				return false;
			}
			else if (n == 2) {
				return true;
			}
			else if (~n & 1) {
				return false;
			}
			u64 d = n - 1;
			u64 q = __builtin_ctz(d);
			d >>= q;

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

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



        constexpr bool is_prime(const u64& n) {
			if (n < (1uL << 31))return miller_rabin_int(n);
			else return miller_rabin_long(n);
        }
    };
};
///@brief fast prime check(MillerRabinの素数判定)

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        uint64_t xi;
        scanf("%lld", &xi);
        printf("%lld ", xi);
        if (prime::miller::is_prime(xi)) {
            puts("1");
        }
        else {
            puts("0");
        }
    }
}
0