結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー satonakatakumi
提出日時 2021-08-21 11:13:17
言語 C
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,744 bytes
コンパイル時間 458 ms
コンパイル使用メモリ 32,512 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-15 02:29:56
合計ジャッジ時間 903 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef int8_t i8;
typedef int16_t i16;
typedef int32_t i32;
typedef int64_t i64;
typedef __int128_t i128;
typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef __uint128_t u128;

typedef struct Montgomery64 {
  u64 m, r, n2;
  u64 x;
} m64;

u64 MR(m64 m_, u128 b) { return (b + (u128)((u64)b * m_.r) * m_.m) >> 64; }
u64 RM(m64 m_) { u64 y = MR(m_, m_.x); return y >= m_.m ? y - m_.m : y; }

m64 make_montgomery(u64 n, u64 mod) {
  m64 result;
  assert(mod != 0);
  assert((mod & 1) != 0);
  result.m = mod;
  result.n2 = -(u128)(mod) % mod;
  result.r = mod;
  for (int _ = 0; _ < 5; _++)
    result.r *= 2 - result.m * result.r;
  result.r = -result.r;
  result.x = MR(result, (u128)n * result.n2);
  return result;
}

m64 plusmod(m64 p, m64 q) { p.x += q.x - (q.m << 1); p.x = ((i64)p.x < 0 ? p.x + (p.m << 1) : p.x); return p; }
m64 minusmod(m64 p, m64 q) { p.x -= q.x; p.x = ((i64)p.x < 0 ? p.x + (p.m << 1) : p.x); return p; }
m64 mulmod(m64 p, m64 q) { p.x = MR(p, (u128)p.x * q.x); return p; }
m64 powmod(m64 p, u64 n) { m64 y = make_montgomery(1, p.m); m64 z = p; for (; n; n >>= 1, z = mulmod(z, z)) if (n & 1) y = mulmod(y, z); return y; }
bool eq(m64 p, m64 q) { return (p.x >= p.m ? p.x - p.m : p.x) == (q.x >= q.m ? q.x - q.m : q.x); }
bool not_eq(m64 p, m64 q) { return !eq(p, q); }


bool is_prime(const u64 n) {
  if (n == 2 || n == 3 || n == 5 || n == 7) return true;
  if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0) return false;
  if (n < 121) return n > 1;
  const u64 m = n - 1;
  const u64 d = m >> __builtin_ctzll(m);
  const m64 one = make_montgomery(1, n), minus_one = make_montgomery(m, n);
  const u64 check1[3] = {2, 7, 61};
  const u64 check2[7] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
  if (n < (1ull << 32)) {
    for (int i = 0; i < 3; i++) {
      m64 a = make_montgomery(check1[i], n);
      m64 y = powmod(a, d);
      u64 t = d;
      while (not_eq(y, one) && not_eq(y, minus_one) && t != m) y = mulmod(y, y), t <<= 1;
      if (not_eq(y, minus_one) && t % 2 == 0) return false;
    }
  } else {
    for (int i = 0; i < 7; i++) {
      if (n <= check2[i]) return true;
      m64 a = make_montgomery(check2[i], n);
      m64 y = powmod(a, d);
      u64 t = d;
      while (not_eq(y, one) && not_eq(y, minus_one) && t != m) y = mulmod(y, y), t <<= 1;
      if (not_eq(y, minus_one) && t % 2 == 0) return false;
    }
  }
  return true;
}


int main() {
  int i, n; scanf("%d", &n);
  u64 u;
  for (i = 0; i < n; i++) {
    scanf("%lu", &u);
    printf("%lu ", u);
    if (is_prime(u)) printf("1\n");
    else printf("0\n");
  }
  return 0;
}
0