結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー nonamaenonamae
提出日時 2021-10-31 12:40:50
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 33 ms / 9,973 ms
コード長 4,335 bytes
コンパイル時間 514 ms
コンパイル使用メモリ 57,472 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-16 23:43:27
合計ジャッジ時間 1,127 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 22 ms
5,248 KB
testcase_05 AC 22 ms
5,248 KB
testcase_06 AC 14 ms
5,248 KB
testcase_07 AC 14 ms
5,248 KB
testcase_08 AC 13 ms
5,248 KB
testcase_09 AC 33 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdint>
#include <cstdio>
#include <map>
#include <utility>
#include <vector>

template<typename T> using V = std::vector<T>;
using i8 = std::int8_t; using u8 = std::uint8_t; using i16 = std::int16_t; using u16 = std::uint16_t; using i32 = std::int32_t; using u32 = std::uint32_t; using i64 = std::int64_t; using u64 = std::uint64_t; using i128 = __int128_t; using u128 = __uint128_t;
using f32 = float; using f64 = double; using f80 = long double;

template<typename T>
T bin_gcd(T a, T b) {
  if (!a || !b) return a | b;
  T shift = CTZ(a | b);
  a >>= CTZ(a);
  do {
    b >>= CTZ(b);
    if (a > b) {
      T t = a;
      a = b;
      b = t;
    }
    b -= a;
  } while (b);
  return a << shift;
}

template<typename Unsigned, typename DoubleUnsigned, typename Signed>
struct Montgomery_t {
  
  Unsigned x;
  
  static Unsigned mod;
  static Unsigned r2;
  static Unsigned inv;
  
  static constexpr int unsigned_bits = sizeof(Unsigned) * 8;
  
  static Unsigned modulus() {
    return mod;
  }
  static Unsigned reduce(DoubleUnsigned x) {
    Unsigned y = Unsigned(x >> unsigned_bits) - Unsigned((DoubleUnsigned(Unsigned(x) * inv) * mod) >> unsigned_bits);
    return Signed(y) < 0 ? y + mod : y;
  }
  static Unsigned to_montgomery(Unsigned w) {
    return reduce(DoubleUnsigned(w) * r2);
  }
  static Unsigned mul_inv(Unsigned n) {
    Unsigned u = 1, v = 0, x = 1ul << (unsigned_bits - 1);
    for (int i = 0; i < unsigned_bits; i++) {
      if (u & 1) u = (u + mod) >> 1, v = (v >> 1) + x;
      else u >>= 1, v >>= 1;
    }
    return -v;
  }
  static void set_mod(Unsigned m) {
    mod = m;
    inv = mul_inv(mod);
    r2 = -DoubleUnsigned(mod) % mod;
  }
  
  Montgomery_t(): x(0) { }
  Montgomery_t(Unsigned _x): x(to_montgomery(_x)) { }
  
  bool operator==(const Montgomery_t& rhs) const {
    return x == rhs.x;
  }
  bool operator!=(const Montgomery_t& rhs) const {
    return x != rhs.x;
  }
  Montgomery_t& operator+=(const Montgomery_t& rhs) {
    x += rhs.x - mod;
    if (Signed(x) < 0) x += mod;
    return *this;
  }
  Montgomery_t& operator-=(const Montgomery_t& rhs) {
    if (Signed(x -= rhs.x) < 0) x += 2 * mod;
    return *this;
  }
  Montgomery_t& operator*=(const Montgomery_t& rhs) {
    x = reduce(DoubleUnsigned(x) * rhs.x);
    return *this;
  }
  Montgomery_t operator+(const Montgomery_t &rhs) const { return Montgomery_t(*this) += rhs; }
  Montgomery_t operator-(const Montgomery_t &rhs) const { return Montgomery_t(*this) -= rhs; }
  Montgomery_t operator*(const Montgomery_t &rhs) const { return Montgomery_t(*this) *= rhs; }
  Montgomery_t operator-() const { return Montgomery_t() - Montgomery_t(*this); }
  Montgomery_t pow(u64 e) const {
    Montgomery_t ret{1};
    for (Montgomery_t base = *this; e; e >>= 1, base *= base) if (e & 1) ret *= base;
    return ret;
  }
  Montgomery_t inverse() const { return pow(mod - 2); }
  Montgomery_t& operator/=(const Montgomery_t& rhs) {
    *this *= rhs.inverse();
    return *this;
  }
  Montgomery_t operator/(const Montgomery_t &rhs) const { return Montgomery_t(*this) /= rhs; }
  
  Unsigned from_montgomery() const { return reduce(x); }
};
using m32 = Montgomery_t<u32, u64, i32>;
template<> u32 m32::mod = 0;
template<> u32 m32::inv = 0;
template<> u32 m32::r2 = 0;
using m64 = Montgomery_t<u64, u128, i64>;
template<> u64 m64::mod = 0;
template<> u64 m64::inv = 0;
template<> u64 m64::r2 = 0;

template<typename Unsigned, typename mint>
bool miller_rabin(Unsigned N, const V<u32>& bases) {
  mint::set_mod(N);
  Unsigned M = N - 1;
  int s = __builtin_ctzll(N - 1);
  Unsigned d = (N - 1) >> s;
  mint one{1}, rev{N - 1};
  for (const auto& base : bases) {
    if (N <= base) break;
    u64 t = d;
    mint y = mint(base).pow(t);
    while (t != M && y != one && y != rev) {
      y *= y;
      t <<= 1;
    }
    if (y != rev && (!(t & 1))) return false;
  }
  return true;
}
bool is_prime(u64 N) {
  if (N <= 3ul) return N == 2ul || N == 3ul;
  if (!(N & 1)) return false;
  if (N < (1u << 31)) return miller_rabin<u32, m32>(u32(N), {2u, 7u, 61u});
  return miller_rabin<u64, m64>(N, {2u, 325u, 9375u, 28178u, 450775u, 9780504u, 1795265022u});
}

void Solve(void) {
  int T; scanf("%d", &T);
  while (T--) {
    u64 N; scanf("%llu", &N);
    printf("%llu %d\n", N, is_prime(N));
  }
}

int main(void) {
  Solve();
  return 0;
}
0