結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー haskellerhaskeller
提出日時 2021-09-01 01:58:21
言語 C
(gcc 12.3.0)
結果
WA  
実行時間 -
コード長 2,644 bytes
コンパイル時間 541 ms
コンパイル使用メモリ 34,688 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-26 14:38:13
合計ジャッジ時間 3,202 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 AC 1 ms
6,820 KB
testcase_02 AC 1 ms
6,816 KB
testcase_03 AC 1 ms
6,820 KB
testcase_04 AC 392 ms
6,820 KB
testcase_05 AC 391 ms
6,820 KB
testcase_06 AC 177 ms
6,820 KB
testcase_07 AC 177 ms
6,820 KB
testcase_08 AC 178 ms
6,820 KB
testcase_09 AC 704 ms
6,820 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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:32:5: warning: implicit declaration of function 'putchar_unlocked' [-Wimplicit-function-declaration]
   32 |     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 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 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);
}

u64 powmod(u128 x, u64 y, u64 m) {
	u128 z = 1;
	for (; y; y >>= 1) {
		if (y & 1) z = z * x % m;
		x = x * x % m;
	}
	return z;
}

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

int is_prime(u64 N) {
  if (N <= 1) return 0;
  if (N == 2) return 1;
  if (N == 3) return 1;
  if (!(N & 1)) return 0;
  u64 m = N - 1;
  u64 s = ctz(m);
  u64 d = m >> s;
  u64 a[] = {2,325,9375,28178,450775,9780504,1795265022};
  int ret = 1;
  for (int i = 0; i < 7; i++) {
    if (ret && a[i] < N) {
      int check1 = powmod(a[i], d, N) != 1;
      int check2 = 1;
      for (int r = 0; r < s; r++) check2 &= (powmod(a[i], ((1 << r) * d), N) != m);
      if (check1 && check2) ret = 0;
    }
  }
  return ret;
}

void Main(void) {
  u64 n = Scanner();
  while (n--) {
    u64 x = Scanner();
    Printer(x);
    putchar_unlocked(' ');
    Printer(is_prime(x));
    newline();
  }
}

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