結果
問題 | No.8030 ミラー・ラビン素数判定法のテスト |
ユーザー | AC2K |
提出日時 | 2023-03-31 11:53:31 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,958 bytes |
コンパイル時間 | 2,635 ms |
コンパイル使用メモリ | 244,952 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-22 16:50:30 |
合計ジャッジ時間 | 3,294 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
ソースコード
#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; 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 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; } bool is_prime(const u64& n) { return miller_rabin_int(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"); } } }