結果
| 問題 | No.3030 ミラー・ラビン素数判定法のテスト |
| ユーザー |
 nonamae
|
| 提出日時 | 2021-10-03 07:26:52 |
| 言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,737 bytes |
| コンパイル時間 | 877 ms |
| コンパイル使用メモリ | 60,404 KB |
| 実行使用メモリ | 4,504 KB |
| 最終ジャッジ日時 | 2023-09-28 06:49:00 |
| 合計ジャッジ時間 | 2,003 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge11 |
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
ソースコード
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <assert.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
/* signed integer */
typedef int8_t i8;
typedef int16_t i16;
typedef int32_t i32;
typedef int64_t i64;
typedef __int128_t i128;
/* unsigned integer */
typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef __uint128_t u128;
/* floating point number */
typedef float f32;
typedef double f64;
typedef long double f80;
typedef int FastInt;
/* io */
static inline FastInt read_int(void) {
FastInt 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;
}
static inline i64 in(void) {
i64 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;
}
static inline u64 inu(void) {
u64 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;
}
static inline void write_int(FastInt x) {
if (x < 0) {
putchar_unlocked('-');
x = -x;
}
if (x >= 10) write_int(x / 10);
putchar_unlocked(x - x / 10 * 10 + 48);
}
static inline void out(i64 x) {
if (x < 0) {
putchar_unlocked('-');
x = -x;
}
if (x >= 10) out(x / 10);
putchar_unlocked(x - x / 10 * 10 + 48);
}
static inline void outu(u64 x) {
if (x >= 10) outu(x / 10);
putchar_unlocked(x - x / 10 * 10 + 48);
}
static inline void NL(void) { putchar_unlocked('\n'); }
static inline void SP(void) { putchar_unlocked(' '); }
/* MACROS */
#define POPCNT(a) __builtin_popcountll((a))
#define CTZ(a) __builtin_ctzll((a))
#define CLZ(a) __builtin_clzll((a))
#define LSBit(a) ((a)&(-(a)))
#define CLSBit(a) ((a)&((a)-(1)))
#define HAS_SINGLE_BIT(a) (POPCNT((a))==1)
#define BIT_CEIL(a) ((!(a))?(1):((POPCNT(a))==(1)?((1ull)<<((63)-CLZ((a)))):((1ull)<<((64)-CLZ(a)))))
#define BIT_FLOOR(a) ((!(a))?(0):((1ull)<<((63)-CLZ((a)))))
#define BIT_WIDTH(a) ((a)?((64)-CLZ((a))):(0))
#define _ROTL(x, s) (((x)<<((s)%(64)))|(((x)>>((64)-((s)%(64))))))
#define _ROTR(x, s) (((x)>>((s)%(64)))|(((x)<<((64)-((s)%(64))))))
#define ROTL(x, s) (((s)==(0))?(0):(((s)<(0))?(_ROTR((x),-(s))):(_ROTL((x),(s)))))
#define ROTR(x, s) (((s)==(0))?(0):(((s)<(0))?(_ROTL((x),-(s))):(_ROTR((x),(s)))))
#define SWAP(a, b) (((a)^=(b)),((b)^=(a)),((a)^=(b)))
#define MAX(a, b) ((a)>(b)?(a):(b))
#define MIN(a, b) ((a)<(b)?(a):(b))
u64 _gcd_(u64 a, u64 b) {
if (!a || !b) return a | b;
FastInt shift = CTZ(a | b);
a >>= CTZ(a);
do {
b >>= CTZ(b);
if (a > b) SWAP(a, b);
b -= a;
} while (b);
return a << shift;
}
u64 _lcm_(u64 a, u64 b) {
return a / _gcd_(a, b) * b;
}
u64 _inv(u64 mod) {
FastInt i;
u64 u = 1, v = 0, x = 1ULL << 63;
for (i = 0; i < 64; i++) {
if (u & 1) u = (u + mod) >> 1, v = (v >> 1) + x;
else u >>= 1, v >>= 1;
}
return -v;
}
u64 _r2(u64 mod) {
return (u128)(i128)-1 % mod + 1;
}
u64 _one(u64 mod) {
return -1ULL % mod + 1;
}
u64 _MR(u128 x, u64 inv, u64 mod) {
i64 z = (x >> 64) - ((((u64)x * inv) * (u128)mod) >> 64);
return z < 0 ? z + mod : (u64)z;
}
u64 to_montgomery_form(u64 a, u64 r2, u64 inv, u64 mod) {
return _MR((u128)a * r2, inv, mod);
}
u64 from_montgomery_form(u64 a, u64 inv, u64 mod) {
return _MR((u128)a, inv, mod);
}
u64 mulmod_MR(u64 x, u64 y, u64 r2, u64 inv, u64 mod) {
return _MR((u128)r2 * _MR((u128)x * y, inv, mod), inv, mod);
}
u64 powmod_MR(u64 a, u64 n, u64 r2, u64 inv, u64 mod) {
u64 res = _one(mod);
u64 A = to_montgomery_form(a, r2, inv, mod);
while (n > 0) {
if (n & 1) res = _MR((u128)res * A, inv, mod);
A = _MR((u128)A * A, inv, mod);
n >>= 1;
}
return from_montgomery_form(res, inv, mod);
}
bool is_prime(u64 n) {
if (n <= 3) return n == 2 || n == 3;
if (!(n & 1)) return false;
u64 r2 = _r2(n);
u64 inv = _inv(n);
u64 s = CTZ(n - 1);
u64 d = (n - 1) >> s;
if (n < (1ull << 30)) {
u64 as[] = {2,7,61};
for (FastInt i = 0; i < 3; i++) {
if (_MR(as[i], inv, n) == 0) return true;
u64 res = powmod_MR(as[i], d, r2, inv, n);
if (res == 1) continue;
bool ok = true;
for (u64 r = 0; r < s; r++) {
if (res == n - 1) {
ok = false;
break;
}
res = mulmod_MR(res, res, r2, inv, n);
}
if (ok) return false;
}
return true;
} else {
u64 as[] = {2,325,9375,28178,450775,9780504,1795265022};
for (FastInt i = 0; i < 7; i++) {
if (_MR(as[i], inv, n) == 0) return true;
u64 res = powmod_MR(as[i], d, r2, inv, n);
if (res == 1) continue;
bool ok = true;
for (u64 r = 0; r < s; r++) {
if (res == n - 1) {
ok = false;
break;
}
res = mulmod_MR(res, res, r2, inv, n);
}
if (ok) return false;
}
return true;
}
}
u64 invmod_MR(u64 a, u64 r2, u64 inv, u64 mod) {
// assert(is_prime(mod));
if (_gcd_(a, mod) != 1) return -1;
return powmod_MR(a, mod - 2, r2, inv, mod);
}
u64 divmod_MR(u64 x, u64 y, u64 r2, u64 inv, u64 mod) {
// assert(is_prime(mod));
u64 z = powmod_MR(y, mod - 2, r2, inv, mod);
return mulmod_MR(x, z, r2, inv, mod);
}
void Main(void) {
FastInt Q = read_int();
while (Q--) {
u64 x = inu();
outu(x); SP(); outu(is_prime(x));
NL();
}
}
int main(void) {
return 0;
}