結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー nonamaenonamae
提出日時 2021-11-03 15:33:06
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 29 ms / 9,973 ms
コード長 5,429 bytes
コンパイル時間 694 ms
コンパイル使用メモリ 58,832 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-16 23:43:45
合計ジャッジ時間 1,382 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#pragma GCC target("avx2")
#pragma GCC optimize("O3")

#pragma region header
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <array>
#include <utility>
#include <vector>
#pragma endregion header

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

#pragma region io
template<typename Int>
Int read_int(void) {
  Int c, x = 0, f = 1;
  while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f;
  while (47 < c && c < 58) {
    x = x * 10 + c - 48;
    c = getchar_unlocked();
  }
  return f * x;
}
template<typename Int>
void write_int(Int x) {
  if (x < 0) {
    putchar_unlocked('-');
    x = -x;
  }
  if (x >= 10) write_int(x / 10);
  putchar_unlocked(x - x / 10 * 10 + 48);
}
template<typename Unsigned>
Unsigned read_uint(void) {
  Unsigned c, x = 0;
  while (c = getchar_unlocked(), c < 48 || c > 57);
  while (47 < c && c < 58) {
    x = x * 10 + c - 48;
    c = getchar_unlocked();
  }
  return x;
}
template<typename Unsigned>
void write_uint(Unsigned x) {
  if (x >= 10) write_uint(x / 10);
  putchar_unlocked(x - x / 10 * 10 + 48);
}
void NL() { putchar_unlocked('\n'); }
void SP() { putchar_unlocked(' '); }
#pragma endregion io

#pragma region binary_gcd
template<typename T>
T bin_gcd(T a, T b) {
  if (!a || !b) return a | b;
  T shift = __builtin_ctzll(a | b);
  a >>= __builtin_ctzll(a);
  do {
    b >>= __builtin_ctzll(b);
    if (a > b) {
      T t = a;
      a = b;
      b = t;
    }
    b -= a;
  } while (b);
  return a << shift;
}
#pragma endregion binary_gcd

#pragma region dynamic montgomery modint
template<typename Word, typename DWord, typename Int>
struct RuntimeModInt {
  
  static Word mod, inv, r2;
  Word x;

  RuntimeModInt() : x(0) {}
  RuntimeModInt(Word _x) : x(init(_x)) {}
  bool operator==(const RuntimeModInt &rhs) const {
    return x == rhs.x;
  }
  bool operator!=(const RuntimeModInt &rhs) const {
    return x != rhs.x;
  }
  RuntimeModInt operator-() const {
    return RuntimeModInt() - RuntimeModInt(*this);
  }
  RuntimeModInt &operator+=(const RuntimeModInt &rhs) {
    if (Int(x += rhs.x - 2 * mod) < 0) x += 2 * mod;
    return *this;
  }
  RuntimeModInt &operator-=(const RuntimeModInt &rhs) {
    if (Int(x -= rhs.x) < 0) x += 2 * mod;
    return *this;
  }
  RuntimeModInt &operator*=(const RuntimeModInt &rhs) {
    x = reduce(DWord(x) * rhs.x);
    return *this;
  }
  RuntimeModInt &operator/=(const RuntimeModInt &rhs) {
    *this *= rhs.inverse();
    return *this;
  }
  RuntimeModInt operator+(const RuntimeModInt &rhs) const {
    return ModInt(*this) += rhs;
  }
  RuntimeModInt operator-(const RuntimeModInt &rhs) const {
    return RuntimeModInt(*this) -= rhs;
  }
  RuntimeModInt operator*(const RuntimeModInt &rhs) const {
    return RuntimeModInt(*this) *= rhs;
  }
  RuntimeModInt operator/(const RuntimeModInt &rhs) const {
    return RuntimeModInt(*this) /= rhs;
  }
  RuntimeModInt pow(u64 e) const {
    RuntimeModInt ret{1};
    for (RuntimeModInt base = *this; e; e >>= 1, base *= base) {
      if (e & 1) ret *= base;
    }
    return ret;
  }
  RuntimeModInt inverse() const {
    return pow(mod - 2);
  }
  Word get() const {
    return reduce(x);
  }
  static constexpr int word_bits = sizeof(Word) * 8;
  static Word get_mod() {
    return mod;
  }
  static Word get_r(Word m) {
    Word ret = m;
    for (i64 i = 0; i < 5; ++i) ret *= 2 - m * ret;
    return ret;
  }
  static Word get_inv() {
    return -DWord(mod) % mod;
  }
  static Word init(Word w) {
    return reduce(DWord(w) * r2);
  }
  static void set_mod(Word m) {
    mod = m;
    inv = get_r(mod);
    r2 = -DWord(mod) % mod;
  }
  static Word reduce(DWord x) {
    Word y = Word(x >> word_bits) - Word((DWord(Word(x) * inv) * mod) >> word_bits);
    return Int(y) < 0 ? y + mod : y;
  }
};

using m64 = RuntimeModInt<u64, u128, i64>;
template<> u64 m64::mod = 0;
template<> u64 m64::inv = 0;
template<> u64 m64::r2 = 0;

using m32 = RuntimeModInt<u32, u64, i32>;
template<> u32 m32::mod = 0;
template<> u32 m32::inv = 0;
template<> u32 m32::r2 = 0;
#pragma endregion dynamic montgomery modint

#pragma region Miller_Rabin primary test
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});
}
#pragma endregion Miller_Rabin primary test

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