結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー kaoru muratakaoru murata
提出日時 2021-09-01 15:13:16
言語 C
(gcc 12.3.0)
結果
WA  
実行時間 -
コード長 4,068 bytes
コンパイル時間 550 ms
コンパイル使用メモリ 34,816 KB
実行使用メモリ 8,352 KB
最終ジャッジ日時 2024-05-05 18:42:45
合計ジャッジ時間 12,177 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 TLE -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'Scanner':
main.c:23:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration]
   23 |   while (c = getchar_unlocked(), c < 48 || c > 57) if (c == 45) f = -f;
      |              ^~~~~~~~~~~~~~~~
main.c: In function 'Printer':
main.c:41:5: warning: implicit declaration of function 'putchar_unlocked' [-Wimplicit-function-declaration]
   41 |     putchar_unlocked('-');
      |     ^~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <assert.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.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;

static i64 Scanner(void) {
  i64 x = 0, f = 1, c;
  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;
}
static u64 ScannerU(void) {
  u64 x = 0, c;
  while (c = getchar_unlocked(), c < 48 || c > 57);
  while (47 < c && c < 58) {
    x = x * 10 + c - 48;
    c = getchar_unlocked();
  }
  return x;
}
static void Printer(i64 x) {
  if (x < 0) {
    putchar_unlocked('-');
    x = -x;
  }
  if (x >= 10) {
    Printer(x / 10);
  }
  putchar_unlocked(x - x / 10 * 10 + 48);
}
static void PrinterU(u64 x) {
  if (x >= 10) {
    Printer(x / 10);
  }
  putchar_unlocked(x - x / 10 * 10 + 48);
}
static void newline(void) {
  putchar_unlocked('\n');
}

static inline u64 ctz(u64 n) { return __builtin_ctzll(n); }
static inline u64 clz(u64 n) { return __builtin_clzll(n); }
static inline u64 popcnt(u64 n) { return __builtin_popcountll(n); }
u64 binary_gcd(u64 u, u64 v) {
  int shl = 0;
  while (u && v && u != v) {
    bool eu = !(u & 1);
    bool ev = !(v & 1);
    if (eu && ev) {
      ++shl;
      u >>= 1;
      v >>= 1;
    }
    else if (eu && !ev) u >>= 1;
    else if (!eu && ev) v >>= 1;
    else if (u >= v) u = (u - v) >> 1;
    else {
      int tmp = u;
      u = (v - u) >> 1;
      v = tmp;
    }
  }
  return !u ? v << shl : u << shl;
}
u64 binary_lcm(u64 u, u64 v) {
  return u / binary_gcd(u, v) * v;
}
i32 ceil_pow2_32(i32 n) {
  return n <= 1 ? 0 : 32 - __builtin_clz(n - 1);
}
i64 ceil_pow2_64(i64 n) {
  return n <= 1 ? 0 : 64 - __builtin_clzl(n - 1);
}

static u64 _rng = 88172645463325252ULL;
u64 next_rand(void) {
  _rng = _rng ^ (_rng << 7);
  return _rng = _rng ^ (_rng >> 9);
}

typedef u64 m64;

u64 mul_inv(u64 n) {
  u64 x = 1;
  for (int i = 6; i > 0; --i) {
    x = x * (2 - x * n);
  }
  return x;
}
m64 calc_mod(u64 m) {
  return m;
}
m64 calc_inv(u64 m) {
  return mul_inv(calc_mod(m));
}
m64 calc_r2(u64 m) {
  return -(u128)(calc_mod(m)) % calc_mod(m);
}
m64 MR(u128 x, m64 mod, m64 inv) {
  m64 y = (u64)(x >> 64) - (u64)(((u128)((u64)x * inv) * mod) >> 64);
  return (i64)y < 0 ? y + mod : y;
}
m64 toM64(u64 w, m64 mod, m64 inv, m64 r2) { return MR((u128)w * r2, mod, inv); }
u64 fromM64(m64 x, m64 mod, m64 inv) { return MR((u128)x, mod, inv); }
m64 addmod(m64 x, m64 y, m64 mod) {
  return (x + y >= mod) ? x + y - mod: x + y;
}
m64 submod(m64 x, m64 y, m64 mod) {
  return (i64)(x - y) < 0 ? x - y + mod : x - y;
}
m64 mulmod(m64 x, m64 y, m64 mod, m64 inv) {
  return MR((u128)x * y, mod, inv);
}
m64 powmod(m64 x, int i, m64 mod, m64 inv, m64 r2) {
  m64 ret = toM64(1, mod, inv, r2);
  for (; i; i >>= 1) {
    if (i & 1) ret = mulmod(ret, x, mod, inv);
    x = mulmod(x, x, mod, inv);
  }
  return ret;
}

bool is_prime(u64 n) {
  if (n < 10) return n == 2 || n == 3 || n == 5 || n == 7;
  if (n % 2 == 0) return false;
  u64 mod = calc_mod(n);
  u64 inv = calc_inv(n);
  u64 r2 = calc_r2(n);
  u64 m = n - 1;
  u64 s = __builtin_ctzll(m);
  u64 d = m >> s;
  m64 one = toM64(1, mod, inv, r2);
  m64 mone = toM64(m, mod, inv, r2);
  u64 a[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
  for (int i = 0; i < 7; i++) {
    if (n <= a[i]) break;
    m64 r = powmod(toM64(a[i], mod, inv, r2), d, mod, inv, r2);
    if (r == one || r == mone) continue;
    int t = s;
    for (; t; t--) {
      r = mulmod(r, r, mod, inv);
      if (r == mone) break;
    }
    if (!t) return false;
  }
  return true;
}

void Main(void) {
  u64 Query = ScannerU();
  while (Query--) {
    u64 x = ScannerU();
    PrinterU(x);
    putchar_unlocked(' ');
    PrinterU(is_prime(x));
    newline();
  }
}

int main() {
  Main();
  return 0;
}
0