結果
| 問題 |
No.8030 ミラー・ラビン素数判定法のテスト
|
| ユーザー |
 magicalkozo
|
| 提出日時 | 2023-08-10 00:58:12 |
| 言語 | C (gcc 13.3.0) |
| 結果 |
AC
|
| 実行時間 | 27 ms / 9,973 ms |
| コード長 | 56,877 bytes |
| コンパイル時間 | 2,833 ms |
| コンパイル使用メモリ | 58,976 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-11-15 23:39:38 |
| 合計ジャッジ時間 | 2,941 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 10 |
ソースコード
#define ONLINE
// #define OFFLINE
#define USE_RNGs
#define USE_GCD
#define USE_POW_ROOT
#define USE_QUADRATIC_RESIDUE
#define USE_COMBSORT11
#define USE_M32
#define USE_M64
#define USE_B32
#define USE_B64
#define USE_DM32
#define USE_DM64
#if defined(ONLINE)
#pragma GCC optimize("O3")
#pragma GCC target("avx512f")
#pragma GCC target("tune=native")
#pragma GCC target("lzcnt")
#pragma GCC target("popcnt")
#endif
#include <assert.h>
#include <ctype.h>
#include <inttypes.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#if defined(ONLINE)
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>
#endif
// clang-format off
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 float f32;
typedef double f64;
typedef struct { i32 a, b; } Pair_i32;
typedef struct { i64 a, b; } Pair_i64;
typedef struct { u32 a, b; } Pair_u32;
typedef struct { u64 a, b; } Pair_u64;
typedef struct { i32 a, b, c; } Triple_i32;
typedef struct { i64 a, b, c; } Triple_i64;
typedef struct { u32 a, b, c; } Triple_u32;
typedef struct { u64 a, b, c; } Triple_u64;
typedef struct { i32 a, b, c, d; } Quadruple_i32;
typedef struct { i64 a, b, c, d; } Quadruple_i64;
typedef struct { u32 a, b, c, d; } Quadruple_u32;
typedef struct { u64 a, b, c, d; } Quadruple_u64;
#define ctz32(a) ((a) ? __builtin_ctz((a)) : (32))
#define clz32(a) ((a) ? __builtin_clz((a)) : (32))
#define pct32(a) __builtin_popcount((a))
#define msb32(a) ((a) ? ((31) - __builtin_clz((a))) : (0))
#define bit_width32(a) ((a) ? ((32) - __builtin_clz((a))) : (0))
#define bit_ceil32(a) ((!(a)) ? (1) : ((pct32(a)) == (1) ? ((1u) << ((31) - clz32((a)))) : ((1u) << ((32) - clz32(a)))))
#define bit_floor32(a) ((!(a)) ? (0) : ((1u) << ((31) - clz32((a)))))
#define ctz64(a) ((a) ? __builtin_ctzll((a)) : (64))
#define clz64(a) ((a) ? __builtin_clzll((a)) : (64))
#define pct64(a) __builtin_popcountll((a))
#define msb64(a) ((a) ? ((63) - __builtin_clzll((a))) : (0))
#define bit_width64(a) ((a) ? ((64) - __builtin_clzll((a))) : (0))
#define bit_ceil64(a) ((!(a)) ? (1) : ((pct64(a)) == (1) ? ((1ull) << ((63) - clz64((a)))) : ((1ull) << ((64) - clz64(a)))))
#define bit_floor64(a) ((!(a)) ? (0) : ((1ull) << ((63) - clz64((a)))))
#define flip_Nbit(a, n) ((a) ^ ((1) << (n)))
#define only_lsb(a) ((a) & (-(a)))
#define bit_reverse32(v) ((((((((((v) & 0x55555555) << 1 | ((v) >> 1 & 0x55555555)) & 0x33333333) << 2 | ((((v) & 0x55555555) << 1 | ((v) >> 1 & 0x55555555)) >> 2 & 0x33333333)) & 0x0f0f0f0f) << 4 | ((((((v) & 0x55555555) << 1 | ((v) >> 1 & 0x55555555)) & 0x33333333) << 2 | ((((v) & 0x55555555) << 1 | ((v) >> 1 & 0x55555555)) >> 2 & 0x33333333)) >> 4 & 0x0f0f0f0f)) & 0x00ff00ff) << 8 | ((((((((v) & 0x55555555) << 1 | ((v) >> 1 & 0x55555555)) & 0x33333333) << 2 | ((((v) & 0x55555555) << 1 | ((v) >> 1 & 0x55555555)) >> 2 & 0x33333333)) & 0x0f0f0f0f) << 4 | ((((((v) & 0x55555555) << 1 | ((v) >> 1 & 0x55555555)) & 0x33333333) << 2 | ((((v) & 0x55555555) << 1 | ((v) >> 1 & 0x55555555)) >> 2 & 0x33333333)) >> 4 & 0x0f0f0f0f)) >> 8 & 0x00ff00ff)) & 0x0000ffff) << 16 | ((((((((((v) & 0x55555555) << 1 | ((v) >> 1 & 0x55555555)) & 0x33333333) << 2 | ((((v) & 0x55555555) << 1 | ((v) >> 1 & 0x55555555)) >> 2 & 0x33333333)) & 0x0f0f0f0f) << 4 | ((((((v) & 0x55555555) << 1 | ((v) >> 1 & 0x55555555)) & 0x33333333) << 2 | ((((v) & 0x55555555) << 1 | ((v) >> 1 & 0x55555555)) >> 2 & 0x33333333)) >> 4 & 0x0f0f0f0f)) & 0x00ff00ff) << 8 | ((((((((v) & 0x55555555) << 1 | ((v) >> 1 & 0x55555555)) & 0x33333333) << 2 | ((((v) & 0x55555555) << 1 | ((v) >> 1 & 0x55555555)) >> 2 & 0x33333333)) & 0x0f0f0f0f) << 4 | ((((((v) & 0x55555555) << 1 | ((v) >> 1 & 0x55555555)) & 0x33333333) << 2 | ((((v) & 0x55555555) << 1 | ((v) >> 1 & 0x55555555)) >> 2 & 0x33333333)) >> 4 & 0x0f0f0f0f)) >> 8 & 0x00ff00ff)) >> 16 & 0x0000ffff)
#define bit_reverse64(v) ((((((((((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) & 0x3333333333333333) << 2 | ((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) >> 2 & 0x3333333333333333)) & 0x0f0f0f0f0f0f0f0f) << 4 | ((((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) & 0x3333333333333333) << 2 | ((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) >> 2 & 0x3333333333333333)) >> 4 & 0x0f0f0f0f0f0f0f0f)) & 0x00ff00ff00ff00ff) << 8 | ((((((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) & 0x3333333333333333) << 2 | ((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) >> 2 & 0x3333333333333333)) & 0x0f0f0f0f0f0f0f0f) << 4 | ((((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) & 0x3333333333333333) << 2 | ((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) >> 2 & 0x3333333333333333)) >> 4 & 0x0f0f0f0f0f0f0f0f)) >> 8 & 0x00ff00ff00ff00ff)) & 0x0000ffff0000ffff) << 16 | ((((((((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) & 0x3333333333333333) << 2 | ((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) >> 2 & 0x3333333333333333)) & 0x0f0f0f0f0f0f0f0f) << 4 | ((((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) & 0x3333333333333333) << 2 | ((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) >> 2 & 0x3333333333333333)) >> 4 & 0x0f0f0f0f0f0f0f0f)) & 0x00ff00ff00ff00ff) << 8 | ((((((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) & 0x3333333333333333) << 2 | ((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) >> 2 & 0x3333333333333333)) & 0x0f0f0f0f0f0f0f0f) << 4 | ((((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) & 0x3333333333333333) << 2 | ((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) >> 2 & 0x3333333333333333)) >> 4 & 0x0f0f0f0f0f0f0f0f)) >> 8 & 0x00ff00ff00ff00ff)) >> 16 & 0x0000ffff0000ffff)) & 0x00000000ffffffff) << 32 | ((((((((((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) & 0x3333333333333333) << 2 | ((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) >> 2 & 0x3333333333333333)) & 0x0f0f0f0f0f0f0f0f) << 4 | ((((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) & 0x3333333333333333) << 2 | ((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) >> 2 & 0x3333333333333333)) >> 4 & 0x0f0f0f0f0f0f0f0f)) & 0x00ff00ff00ff00ff) << 8 | ((((((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) & 0x3333333333333333) << 2 | ((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) >> 2 & 0x3333333333333333)) & 0x0f0f0f0f0f0f0f0f) << 4 | ((((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) & 0x3333333333333333) << 2 | ((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) >> 2 & 0x3333333333333333)) >> 4 & 0x0f0f0f0f0f0f0f0f)) >> 8 & 0x00ff00ff00ff00ff)) & 0x0000ffff0000ffff) << 16 | ((((((((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) & 0x3333333333333333) << 2 | ((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) >> 2 & 0x3333333333333333)) & 0x0f0f0f0f0f0f0f0f) << 4 | ((((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) & 0x3333333333333333) << 2 | ((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) >> 2 & 0x3333333333333333)) >> 4 & 0x0f0f0f0f0f0f0f0f)) & 0x00ff00ff00ff00ff) << 8 | ((((((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) & 0x3333333333333333) << 2 | ((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) >> 2 & 0x3333333333333333)) & 0x0f0f0f0f0f0f0f0f) << 4 | ((((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) & 0x3333333333333333) << 2 | ((((v) & 0x5555555555555555) << 1 | ((v) >> 1 & 0x5555555555555555)) >> 2 & 0x3333333333333333)) >> 4 & 0x0f0f0f0f0f0f0f0f)) >> 8 & 0x00ff00ff00ff00ff)) >> 16 & 0x0000ffff0000ffff)) >> 32 & 0x00000000ffffffff)
#define rotr32(x, r) ((r) < (0) ? (((x) << ((u32)(((u64)(-(r)) % (32))))) | ((x) >> ((-(((u32)(((u64)(-(r)) % (32)))))) & 31))) : (((x) >> ((r) % (32))) | ((x) << ((-(r)) & 31))))
#define rotl32(x, r) (rotr32((x), (-(r))))
#define rotr64(x, r) ((r) < (0) ? (((x) << (((u64)(-(r)) % (64)))) | ((x) >> ((-((((u64)(-(r)) % (64))))) & 63))) : (((x) >> ((r) % (64))) | ((x) << ((-(r)) & 63))))
#define rotl64(x, r) (rotr64((x), (-(r))))
#if defined(OFFLINE)
#if defined(_WIN32)
#define GetChar _getchar_nolock
#define PutChar _putchar_nolock
#else
#define _GNU_SOURCE
#define GetChar getchar_unlocked
#define PutChar putchar_unlocked
#endif
#define INPUT_UINT(bit) \
u##bit c, x = 0; \
while (c = GetChar(), c < '0' || c > '9') { \
} \
while ('/' < c && c < ':') { \
x = x * 10 + c - '0'; \
c = GetChar(); \
} \
return x
u32 in_u32(void) { INPUT_UINT(32); }
u64 in_u64(void) { INPUT_UINT(64); }
u128 in_u128(void) { INPUT_UINT(128); }
#undef INPUT_UINT
#define INPUT_SINT(bit) \
i##bit c, x = 0, f = 1; \
while (c = GetChar(), c < '0' || c > '9') { \
if (c == '-') { \
f = -f; \
} \
} \
while ('/' < c && c < ':') { \
x = x * 10 + c - '0'; \
c = GetChar(); \
} \
return f * x
i32 in_i32(void) { INPUT_SINT(32); }
i64 in_i64(void) { INPUT_SINT(64); }
i128 in_i128(void) { INPUT_SINT(128); }
#undef INPUT_SINT
#define OUTPUT_UINT(bit) \
if (x >= 10) { \
out_u##bit(x / 10); \
} \
PutChar(x - x / 10 * 10 + '0')
void out_u32(u32 x) { OUTPUT_UINT(32); }
void out_u64(u64 x) { OUTPUT_UINT(64); }
void out_u128(u128 x) { OUTPUT_UINT(128); }
#undef OUTPUT_UINT
#define OUTPUT_SINT(bit) \
if (x < 0) { \
PutChar('-'); \
x = -x; \
} \
out_u##bit((u##bit)x)
void out_i32(i32 x) { OUTPUT_SINT(32); }
void out_i64(i64 x) { OUTPUT_SINT(64); }
void out_i128(i128 x) { OUTPUT_SINT(128); }
#undef OUTPUT_SINT
void newline(void) { PutChar('\n'); }
void space(void) { PutChar(' '); }
#define OUTPUT_BINARY(bit) \
u##bit mask = (u##bit)1 << (sizeof(v) * CHAR_BIT - 1); \
do { \
PutChar(mask &v ? '1' : '0'); \
} while (mask >>= 1)
void printb_32bit(u32 v) { OUTPUT_BINARY(32); }
void printb_64bit(u64 v) { OUTPUT_BINARY(64); }
#undef OUTPUT_BINARY
#undef PutChar
#undef GetChar
#endif
#if defined(ONLINE)
static char *input;
static size_t input_size, input_string_size;
__attribute__((constructor)) void _construct_read_(void) {
struct stat st;
fstat(0, &st);
input_string_size = st.st_size - 1;
input_size = st.st_size + 1;
input = (char *)mmap(0, input_size, PROT_READ, MAP_PRIVATE /* MAP_SHARED | MAP_POPULATE */, 0, 0);
if (input == MAP_FAILED)
__builtin_trap();
// madvise(input, input_size, MADV_SEQUENTIAL);
}
#define READ_SKIP \
char c = *input; \
if (c < '!') \
*input++, c = *input;
#define READ_CHAR_TO_INTEGER \
for (*x = *input++ & 15; (c = *input++) >= '0';) \
*x = *x * 10 + (c & 15);
#define READ_UNSIGNED \
READ_SKIP \
READ_CHAR_TO_INTEGER
#define READ_SIGNED \
READ_SKIP \
bool flag = false; \
if (c == '-') { \
flag = true; \
*input++; \
} \
READ_CHAR_TO_INTEGER \
*x = flag ? (*x) * (-1) : *x;
void rd_int(int *x) { READ_SIGNED }
void rd_ll(long long *x) { READ_SIGNED }
void rd_i32(i32 *x) { READ_SIGNED }
void rd_i64(i64 *x) { READ_SIGNED }
void rd_i128(i128 *x) { READ_SIGNED }
void rd_uint(unsigned *x) { READ_UNSIGNED }
void rd_ull(unsigned long long *x) { READ_UNSIGNED }
void rd_u32(u32 *x) { READ_UNSIGNED }
void rd_u64(u64 *x) { READ_UNSIGNED }
void rd_u128(u128 *x) { READ_UNSIGNED }
#undef READ_SIGNED
#undef READ_UNSIGNED
#undef READ_CHAR_TO_INTEGER
#undef READ_SKIP
__attribute__((destructor)) void _destruct_read_(void) {
munmap(input, input_size);
input_size = input_string_size = 0;
}
#define O_BUF_SIZE 1048576
#define O_BLOCK_SIZE 10000
#define O_INT_SIZE 39
static char output[O_BUF_SIZE + 1];
static char output_block_str[O_BLOCK_SIZE * 4 + 1];
static u128 power10[O_INT_SIZE];
static size_t output_size;
__attribute__((constructor)) void _construct_write_(void) {
output_size = 0;
for (size_t i = 0; i < O_BLOCK_SIZE; i++) {
size_t j = 4, k = i;
while (j--) {
output_block_str[i * 4 + j] = k % 10 + '0';
k /= 10;
}
}
power10[0] = 1ull;
for (size_t i = 1; i < O_INT_SIZE; i++)
power10[i] = power10[i - 1] * 10;
}
#define DIGIT_BLOCK1 \
if (n >= power10[9]) return 10; \
if (n >= power10[8]) return 9; \
if (n >= power10[7]) return 8; \
if (n >= power10[6]) return 7; \
if (n >= power10[5]) return 6; \
if (n >= power10[4]) return 5; \
if (n >= power10[3]) return 4; \
if (n >= power10[2]) return 3; \
if (n >= power10[1]) return 2; \
return 1;
#define DIGIT_BLOCK2 \
if (n >= power10[19]) return 20; \
if (n >= power10[18]) return 19; \
if (n >= power10[17]) return 18; \
if (n >= power10[16]) return 17; \
if (n >= power10[15]) return 16; \
if (n >= power10[14]) return 15; \
if (n >= power10[13]) return 14; \
if (n >= power10[12]) return 13; \
if (n >= power10[11]) return 12; \
return 11;
#define DIGIT_BLOCK3 \
if (n >= power10[29]) return 30; \
if (n >= power10[28]) return 29; \
if (n >= power10[27]) return 28; \
if (n >= power10[26]) return 27; \
if (n >= power10[25]) return 26; \
if (n >= power10[24]) return 25; \
if (n >= power10[23]) return 24; \
if (n >= power10[22]) return 23; \
if (n >= power10[21]) return 22; \
return 21;
#define DIGIT_BLOCK4 \
if (n >= power10[38]) return 39; \
if (n >= power10[37]) return 38; \
if (n >= power10[36]) return 37; \
if (n >= power10[35]) return 36; \
if (n >= power10[34]) return 35; \
if (n >= power10[33]) return 34; \
if (n >= power10[32]) return 33; \
if (n >= power10[31]) return 32; \
return 31;
#define OUTPUT_BUFFER_EQ_CHECK \
if (__builtin_expect(output_size == O_BUF_SIZE, 0)) \
flush();
#define OUTPUT_BUFFER_CHECK \
if (__builtin_expect(output_size + O_INT_SIZE >= O_BUF_SIZE, 0)) \
flush();
#define WRITE_PER_4CHARS(bit) \
size_t digit = get_integer_size_##bit(x); \
size_t len = digit; \
while (len >= 4) { \
len -= 4; \
memcpy(output + output_size + len, output_block_str + (x % O_BLOCK_SIZE) * 4, 4); \
x /= O_BLOCK_SIZE; \
} \
memcpy(output + output_size, output_block_str + x * 4 + (4 - len), len); \
output_size += digit;
#define WRITE_UNSIGNED(bit) \
OUTPUT_BUFFER_CHECK \
WRITE_PER_4CHARS(bit)
#define WRITE_SIGNED(bit) \
OUTPUT_BUFFER_CHECK \
if (x < 0) { \
output[output_size++] = '-'; \
x = -x; \
} \
WRITE_PER_4CHARS(bit)
void flush() {
fwrite(output, 1, output_size, stdout);
output_size = 0;
}
size_t get_integer_size_32(u32 n) {
DIGIT_BLOCK1
}
size_t get_integer_size_64(u64 n) {
if (n >= power10[10]) {
DIGIT_BLOCK2
} else {
DIGIT_BLOCK1
}
}
size_t get_integer_size_128(u128 n) {
if (n >= power10[30]) {
DIGIT_BLOCK4
} else if (n >= power10[20]) {
DIGIT_BLOCK3
} else if (n >= power10[10]) {
DIGIT_BLOCK2
} else {
DIGIT_BLOCK1
}
}
void wt_sp(void) {
output[output_size++] = ' ';
OUTPUT_BUFFER_EQ_CHECK
}
void wt_nl(void) {
output[output_size++] = '\n';
OUTPUT_BUFFER_EQ_CHECK
}
void wt_char(char c) {
output[output_size++] = c;
OUTPUT_BUFFER_EQ_CHECK
}
void wt_str(const char* s) {
while (*s != 0) {
output[output_size++] = *s++;
OUTPUT_BUFFER_EQ_CHECK
}
}
void wt_uint(unsigned x) { WRITE_UNSIGNED(32) }
void wt_ull(unsigned long long x) { WRITE_UNSIGNED(64) }
void wt_u32(u32 x) { WRITE_UNSIGNED(32) }
void wt_u64(u64 x) { WRITE_UNSIGNED(64) }
void wt_u128(u128 x) { WRITE_UNSIGNED(128) }
void wt_int(int x) { WRITE_SIGNED(32) }
void wt_ll(long long x) { WRITE_SIGNED(64) }
void wt_i32(i32 x) { WRITE_SIGNED(32) }
void wt_i64(i64 x) { WRITE_SIGNED(64) }
void wt_i128(i128 x) { WRITE_SIGNED(128) }
#undef WRITE_SIGNED
#undef WRITE_UNSIGNED
#undef WRITE_PER_4CHARS
#undef OUTPUT_BUFFER_CHECK
#undef OUTPUT_BUFFER_EQ_CHECK
#undef DIGIT_BLOCK4
#undef DIGIT_BLOCK3
#undef DIGIT_BLOCK2
#undef DIGIT_BLOCK1
#undef O_BUF_SIZE
#undef O_BLOCK_SIZE
#undef O_INT_SIZE
__attribute__((destructor)) void _destruct_write_(void) {
flush();
output_size = 0;
}
#endif
#if defined(USE_RNGs)
#if defined(ONLINE)
u32 rand_32(void) { static u64 lcg_state = 14534622846793005ull; lcg_state = 6364136223846793005ull * lcg_state + 1442695040888963407ull; return (u32)lcg_state; }
u32 randrange_32(u32 l, u32 r) { return l + rand_32() % (r - l + 1); }
f32 randf_32(void) { u32 a = 0x3F800000u | (rand_32() >> 9); return (*((f32 *)(&a))) - 1; }
u64 rand_64(void) { static u64 msws_state1 = 0; static u64 msws_state2 = 0; static u64 msws_state3 = 0xb5ad4eceda1ce2a9ul; static u64 msws_state4 = 0; static u64 msws_state5 = 0; static u64 msws_state6 = 0x278c5a4d8419fe6bul; u64 ret; msws_state1 *= msws_state1; ret = msws_state1 += (msws_state2 += msws_state3); msws_state1 = (msws_state1 >> 32) | (msws_state1 << 32); msws_state4 *= msws_state4; msws_state4 += (msws_state5 += msws_state6); msws_state4 = (msws_state4 >> 32) | (msws_state4 << 32); return ret ^ msws_state4; }
u64 randrange_64(u64 l, u64 r) { return l + rand_64() % (r - l + 1); }
f64 randf_64(void) { u64 a = 0x3FF0000000000000ull | (rand_64() >> 12); return (*((f64 *)(&a))) - 1; }
#else
u32 rand_32(void) { static u64 pcg_state = 0x853c49e6748fea9bull; u64 t = pcg_state; pcg_state = t * 0x5851f42d4c957f2dull + 0xda3e39cb94b95bdbull; u32 sh = ((t >> 18u) ^ t) >> 27u; u32 ro = t >> 59u; return (sh >> ro) | (sh << ((-ro) & 31)); }
u32 randrange_32(u32 l, u32 r) { return l + rand_32() % (r - l + 1); }
f32 randf_32(void) { u32 a = 0x3F800000u | (rand_32() >> 9); return (*((f32 *)(&a))) - 1; }
u64 rand_64(void) { static u64 xrsr128ss_state1 = 0x1ull; static u64 xrsr128ss_state2 = 0x2ull; const u64 s0 = xrsr128ss_state1; u64 s1 = xrsr128ss_state2; const u64 ret = rotl64(s0 * 5, 7) * 9; s1 ^= s0; xrsr128ss_state1 = rotl64(s0, 24) ^ s1 ^ (s1 << 16); xrsr128ss_state2 = rotl64(s1, 37); return ret; }
u64 randrange_64(u64 l, u64 r) { return l + rand_64() % (r - l + 1); }
f64 randf_64(void) { u64 a = 0x3FF0000000000000ull | (rand_64() >> 12); return (*((f64 *)(&a))) - 1; }
#endif
#endif
#if defined(USE_GCD)
#define BGCD(bit) \
if (!a || !b) \
return a | b; \
u##bit t, s = ctz##bit(a | b); \
a >>= ctz##bit(a); \
do { \
b >>= ctz##bit(b); \
if (a > b) \
t = a, a = b, b = t; \
b -= a; \
} while (b); \
return a << s;
u32 gcd32(u32 a, u32 b) {
BGCD(32);
}
u64 gcd64(u64 a, u64 b) {
BGCD(64);
}
#undef BGCD
#endif
#if defined(USE_POW_ROOT)
#define IPOW(bit) \
u##bit p = 1; \
while (k) { \
if (k & 1) \
p *= n; \
k >>= 1; \
if (k) \
n *= n; \
} \
return p;
u32 ipow_u32(u32 n, u64 k) {
IPOW(32);
}
u32 ipow_u64(u32 n, u64 k) {
IPOW(64);
}
#undef IPOW
#define SPOW(bit) \
if (k == 0) \
return 1; \
u##bit res = 1; \
while (k) { \
if (k & 1) \
res = __builtin_mul_overflow_p(res, n, (u##bit)0) ? UINT##bit##_MAX : res * n; \
n = __builtin_mul_overflow_p(n, n, (u##bit)0) ? UINT##bit##_MAX : n * n; \
k >>= 1; \
} \
return res;
u32 spow_u32(u32 n, u32 k) {
SPOW(32);
}
u64 spow_u64(u64 n, u64 k) {
SPOW(64);
}
#undef SPOW
#define POWMOD(word, dword) \
u##word res = 1; \
while (k) { \
if (k & 1) \
res = ((u##dword)n * res) % mod; \
n = ((u##dword)n * n) % mod; \
k >>= 1; \
} \
return res;
u32 powmod_u32(u32 n, u64 k, u32 mod) {
POWMOD(32, 64);
}
u64 powmod_u64(u64 n, u64 k, u64 mod) {
POWMOD(64, 128);
}
#undef POWMOD
u64 isqrt(u64 n) {
u64 root;
if (n >= (u64)(18446744065119617025ull))
return (u64)(4294967295ull);
root = (u64)sqrt((double)n);
if (root * root > n)
root--;
if ((root + 1) * (root + 1) <= n)
root++;
return root;
}
u64 icbrt(u64 n) {
u64 b, root = 0;
int s = 63;
if (n >= (u64)(18446724184312856125ull))
return (u64)(2642245ull);
for (; s >= 0; s -= 3) {
root += root;
b = 3 * root * (root + 1) + 1;
if ((n >> s) >= b) {
n -= b << s;
root++;
}
}
return root;
}
u64 floor_kth_root_integer(u64 a, u64 k) {
if (a <= 1 || k == 1)
return a;
if (k >= 64)
return 1;
if (k == 2)
return isqrt(a);
if (a == UINT64_MAX)
a--;
u64 res = (k == 3 ? icbrt(a) : pow(a, nextafter(1 / (double)k, 0)));
while (spow_u64(res + 1, k) <= a)
res++;
return res;
}
bool is_perfect_square(u64 n) {
u32 m = n & 127;
if ((m * 0x8bc40d7d) & (m * 0xa1e2f5d1) & 0x14020a) return false;
m = n % 240;
if ((m * 0xfa445556) & (m * 0x8021feb1) & 0x614aaa0f) return false;
m = isqrt(n);
return (u64)m * m == n;
}
bool is_perfect_cube(u64 n) {
u32 m;
m = n % 117;
if ((m * 833230740) & (m * 120676722) & 813764715) return false;
m = n % 133;
if ((m * 76846229) & (m * 305817297) & 306336544) return false;
m = n % 43;
if ((m * 193635074) & (m * 3653322805U) & 74401) return false;
m = n % 37;
if ((m * 919307198) & (m * 3908849845U) & 6665) return false;
m = icbrt(n);
return (u64)m * m * m == n;
}
bool is_perfect_fifth(u64 n) {
u64 m;
if ((n & 3) == 2) return false;
m = n % 88;
if ((m * 85413603) & (m * 76260301) & 26476550) return false;
m = n % 31;
if ((m * 80682551) & (m * 73523539) & 45414528) return false;
m = n % 41;
if ((m * 92806493) & (m * 130690042) & 35668129) return false;
m = floor_kth_root_integer(n, 5);
return m * m * m * m * m == n;
}
bool is_perfect_seventh(u64 n) {
u64 m;
m = n & 511;
if ((m * 97259473) & (m * 51311663) & 894)
return false;
m = n % 49;
if ((m * 109645301) & (m * 76482737) & 593520192)
return false;
m = n % 71;
if ((m * 71818386) & (m * 38821587) & 35299393)
return false;
m = floor_kth_root_integer(n, 7);
return m * m * m * m * m * m * m == n;
}
#endif
#if defined(USE_COMBSORT11)
#define COMBSORT11(type) \
int g = a_len; \
type t; \
while (true) { \
bool flag = true; \
g = (((g * 10) / 13) > 1) ? ((g * 10) / 13) : 1; \
if (g == 9 || g == 10) \
g = 11; \
for (int i = 0; i + g < a_len; i++) { \
if (func(a[i], a[i + g])) { \
t = a[i], a[i] = a[i + g], a[i + g] = t; \
flag = false; \
} \
} \
if (g == 1 && flag) \
break; \
}
void combsort11_i32(bool(*func)(i32, i32), int a_len, i32* a) {
COMBSORT11(i32);
}
void combsort11_i64(bool(*func)(i64, i64), int a_len, i64* a) {
COMBSORT11(i64);
}
void combsort11_u32(bool(*func)(u32, u32), int a_len, u32* a) {
COMBSORT11(u32);
}
void combsort11_u64(bool(*func)(u64, u64), int a_len, u64* a) {
COMBSORT11(u64);
}
void combsort11_Pair_i32(bool(*func)(Pair_i32, Pair_i32), int a_len, Pair_i32* a) {
COMBSORT11(Pair_i32);
}
void combsort11_Pair_i64(bool(*func)(Pair_i64, Pair_i64), int a_len, Pair_i64* a) {
COMBSORT11(Pair_i64);
}
void combsort11_Pair_u32(bool(*func)(Pair_u32, Pair_u32), int a_len, Pair_u32* a) {
COMBSORT11(Pair_u32);
}
void combsort11_Pair_u64(bool(*func)(Pair_u64, Pair_u64), int a_len, Pair_u64* a) {
COMBSORT11(Pair_u64);
}
#undef COMBSORT11
#endif
#if defined(USE_M32) || defined(USE_M64) || defined(USE_DM32) || defined(USE_DM64)
typedef struct { i32 a, b; u32 d; } Bezout32;
typedef struct { i64 a, b; u64 d; } Bezout64;
#define BEZOUT(bit) \
u##bit t; \
bool swap = x < y; \
if (swap) t = x, x = y, y = t; \
if (y == 0) \
{ \
if (x == 0) \
return (Bezout##bit) {0, 0, 0}; \
else if (swap) \
return (Bezout##bit) {0, 1, x}; \
else \
return (Bezout##bit) {1, 0, x}; \
} \
i##bit s0 = 1, s1 = 0, t0 = 0, t1 = 1; \
while (true) \
{ \
u##bit q = x / y, r = x % y; \
if (r == 0) \
{ \
if (swap) \
return (Bezout##bit) {t1, s1, y}; \
else \
return (Bezout##bit) {s1, t1, y}; \
} \
i##bit s2 = s0 - (i##bit)(q) * s1, t2 = t0 - (i##bit)(q) * t1; \
x = y, y = r; \
s0 = s1, s1 = s2, t0 = t1, t1 = t2; \
}
static Bezout32 bezout32(u32 x, u32 y) { BEZOUT(32); }
static Bezout64 bezout64(u64 x, u64 y) { BEZOUT(64); }
#undef BEZOUT
u32 modinv32(u32 x, u32 mod) {
Bezout32 abd = bezout32(x, mod);
return abd.a < 0 ? mod + abd.a : (u32)abd.a;
}
u64 modinv64(u64 x, u64 mod) {
Bezout64 abd = bezout64(x, mod);
return abd.a < 0 ? mod + abd.a : (u64)abd.a;
}
#endif
#if defined(USE_M32)
static u32 n_m32, n2_m32, ni_m32, r1_m32, r2_m32, r3_m32;
void set_m32(u32 mod) { if (mod == n_m32) return; n_m32 = mod; n2_m32 = mod << 1; ni_m32 = mod; for (int _ = 0; _ < 4; ++_) ni_m32 *= 2 - ni_m32 * mod; r1_m32 = (u32)(i32)-1 % mod + 1; r2_m32 = (u64)(i64)-1 % mod + 1; r3_m32 = (u32)(((u64)r1_m32 * (u64)r2_m32) % mod); }
static inline u32 mr32(u64 a) { u32 y = (u32)(a >> 32) - (u32)(((u64)((u32)a * ni_m32) * n_m32) >> 32); return (i32)y < 0 ? y + n_m32 : y; }
u32 to_m32(u32 a) { return mr32((u64)a * r2_m32); }
u32 from_m32(u32 a) { return mr32((u64)a); }
u32 add_m32(u32 a, u32 b) { a += b; a -= (a >= n_m32 ? n_m32 : 0); return a; }
u32 sub_m32(u32 a, u32 b) { a += (a < b ? n_m32 : 0); a -= b; return a; }
u32 min_m32(u32 a) { return sub_m32(0, a); }
u32 relaxed_add_m32(u32 a, u32 b) { a += b - n2_m32; a += n2_m32 & -(a >> 31u); return a; }
u32 relaxed_sub_m32(u32 a, u32 b) { a -= b; a += n2_m32 & -(a >> 31u); return a; }
u32 relaxed_min_m32(u32 a) { return relaxed_sub_m32(0, a); }
u32 mul_m32(u32 a, u32 b) { return mr32((u64)a * b); }
u32 squ_m32(u32 a) { return mr32((u64)a * a); }
u32 shl_m32(u32 a) { return (a <<= 1) >= n_m32 ? a - n_m32 : a; }
u32 shr_m32(u32 a) { return (a & 1) ? ((a >> 1) + (n_m32 >> 1) + 1) : (a >> 1); }
u32 pow_m32(u32 a, u64 k) { u32 ret = r1_m32; while (k > 0) { if (k & 1) ret = mul_m32(ret, a); a = squ_m32(a); k >>= 1; } return ret; }
u32 inv_m32(u32 a) { return mr32((u64)r3_m32 * modinv32(a, n_m32)); }
u32 div_m32(u32 a, u32 b) { return mul_m32(a, inv_m32(b)); }
#endif
#if defined(USE_M64)
static u64 n_m64, n2_m64, ni_m64, r1_m64, r2_m64, r3_m64;
void set_m64(u64 mod) { if (mod == n_m64) return; n_m64 = mod; n2_m64 = mod << 1; ni_m64 = mod; for (int _ = 0; _ < 5; ++_) ni_m64 *= 2 - ni_m64 * mod; r1_m64 = (u64)(i64)-1 % mod + 1; r2_m64 = (u128)(i128)-1 % mod + 1; r3_m64 = (u64)(((u128)r1_m64 * (u128)r2_m64) % mod); }
static inline u64 mr64(u128 a) { u64 y = (u64)(a >> 64) - (u64)(((u128)((u64)a * ni_m64) * n_m64) >> 64); return (i64)y < 0 ? y + n_m64 : y; }
u64 to_m64(u64 a) { return mr64((u128)a * r2_m64); }
u64 from_m64(u64 a) { return mr64((u128)a); }
u64 add_m64(u64 a, u64 b) { a += b; a -= (a >= n_m64 ? n_m64 : 0); return a; }
u64 sub_m64(u64 a, u64 b) { a += (a < b ? n_m64 : 0); a -= b; return a; }
u64 min_m64(u64 a) { return sub_m64(0, a); }
u64 relaxed_add_m64(u64 a, u64 b) { a += b - n2_m64; a += n2_m64 & -(a >> 63u); return a; }
u64 relaxed_sub_m64(u64 a, u64 b) { a -= b; a += n2_m64 & -(a >> 63u); return a; }
u64 relaxed_min_m64(u64 a) { return relaxed_sub_m64(0, a); }
u64 mul_m64(u64 a, u64 b) { return mr64((u128)a * b); }
u64 squ_m64(u64 a) { return mr64((u128)a * a); }
u64 shl_m64(u64 a) { return (a <<= 1) >= n_m64 ? a - n_m64 : a; }
u64 shr_m64(u64 a) { return (a & 1) ? ((a >> 1) + (n_m64 >> 1) + 1) : (a >> 1); }
u64 pow_m64(u64 a, u64 k) { u64 ret = r1_m64; while (k > 0) { if (k & 1) ret = mul_m64(ret, a); a = squ_m64(a); k >>= 1; } return ret; }
u64 inv_m64(u64 a) { return mr64((u128)r3_m64 * modinv64(a, n_m64)); }
u64 div_m64(u64 a, u64 b) { return mul_m64(a, inv_m64(b)); }
#endif
#if defined(USE_B32)
static u64 m_b32, m2_b32, im_b32, div_b32, rem_b32;
void set_b32(u64 mod) { if (mod == m_b32) return; m_b32 = mod; m2_b32 = mod << 1; im_b32 = ((((u128)(1ull) << 64)) + mod - 1) / mod; div_b32 = 0; rem_b32 = 0; }
static inline void br32(u64 a) {
u64 x = (u64)(((u128)(a) * im_b32) >> 64);
u64 y = x * m_b32;
unsigned long long z;
#if defined(__GNUC__)
u32 w = __builtin_usubll_overflow(a, y, &z) ? m_b32 : 0;
#else
z = a - y;
u32 w = a < y ? m_b32 : 0;
#endif
div_b32 = x;
rem_b32 = z + w;
}
u32 add_b32(u32 a, u32 b) { a += b; a -= (a >= (u32)m_b32 ? (u32)m_b32 : 0); return a; }
u32 sub_b32(u32 a, u32 b) { a += (a < b ? (u32)m_b32 : 0); a -= b; return a; }
u32 min_b32(u32 a) { return sub_b32(0, a); }
u32 relaxed_add_b32(u32 a, u32 b) { a += b - m2_b32; a += m2_b32 & -(a >> 31u); return a; }
u32 relaxed_sub_b32(u32 a, u32 b) { a -= b; a += m2_b32 & -(a >> 31u); return a; }
u32 relaxed_min_b32(u32 a) { return relaxed_sub_b32(0, a); }
u32 mul_b32(u32 a, u32 b) { br32((u64)a * b); return (u32)rem_b32; }
u32 squ_b32(u32 a) { br32((u64)a * a); return (u32)rem_b32; }
u32 shl_b32(u32 a) { return (a <<= 1) >= m_b32 ? a - m_b32 : a; }
u32 shr_b32(u32 a) { return (a & 1) ? ((a >> 1) + (m_b32 >> 1) + 1) : (a >> 1); }
u32 pow_b32(u32 a, u64 k) { u32 ret = 1u; while (k > 0) { if (k & 1) ret = mul_b32(ret, a); a = squ_b32(a); k >>= 1; } return ret; }
#endif
#if defined(USE_B64)
static u128 m_b64, m2_b64, im_b64, div_b64, rem_b64;
void set_b64(u128 mod) { if (mod == m_b64) return; m_b64 = mod; m2_b64 = mod << 1; im_b64 = (~((u128)0ull)) / mod; div_b64 = 0; rem_b64 = 0; }
static inline void br64(u128 x) { if (m_b64 == 1) { div_b64 = x; rem_b64 = 0; return; } u8 f; u128 a = x >> 64; u128 b = x & 0xffffffffffffffffull; u128 c = im_b64 >> 64; u128 d = im_b64 & 0xffffffffffffffffull; u128 ac = a * c; u128 bd = (b * d) >> 64; u128 ad = a * d; u128 bc = b * c; f = (ad > ((u128)((i128)(-1L)) - bd)); bd += ad; ac += f; f = (bc > ((u128)((i128)(-1L)) - bd)); bd += bc; ac += f; u128 q = ac + (bd >> 64); u128 r = x - q * m_b64; if (m_b64 <= r) { r -= m_b64; q += 1; } div_b64 = q; rem_b64 = r; }
u64 add_b64(u64 a, u64 b) { a += b; a -= (a >= (u64)m_b64 ? (u64)m_b64 : 0); return a; }
u64 sub_b64(u64 a, u64 b) { a += (a < b ? (u64)m_b64 : 0); a -= b; return a; }
u64 min_b64(u64 a) { return sub_b64(0, a); }
u64 relaxed_add_b64(u64 a, u64 b) { a += b - m2_b64; a += m2_b64 & -(a >> 63u); return a; }
u64 relaxed_sub_b64(u64 a, u64 b) { a -= b; a += m2_b64 & -(a >> 63u); return a; }
u64 relaxed_min_b64(u64 a) { return relaxed_sub_b64(0, a); }
u64 mul_b64(u64 a, u64 b) { br64((u128)a * b); return (u64)rem_b64; }
u64 squ_b64(u64 a) { br64((u128)a * a); return (u64)rem_b64; }
u64 shl_b64(u64 a) { return (a <<= 1) >= m_b64 ? a - m_b64 : a; }
u64 shr_b64(u64 a) { return (a & 1) ? ((a >> 1) + (m_b64 >> 1) + 1) : (a >> 1); }
u64 pow_b64(u64 a, u64 k) { u64 ret = 1ull; while (k > 0) { if (k & 1) ret = mul_b64(ret, a); a = squ_b64(a); k >>= 1; } return ret; }
#endif
#if defined(USE_DM32)
u32 r1_dm32(u32 mod) { return (u32)(i32)-1 % mod + 1; }
u32 r2_dm32(u32 mod) { return (u64)(i64)-1 % mod + 1; }
u32 r3_dm32(u32 mod, u32 r1, u32 r2) { return (u32)(((u64)r1 * (u64)r2) % mod); }
u32 n_dm32(u32 mod) { return mod; }
u32 ni_dm32(u32 mod) { u32 ni = mod; for (int _ = 0; _ < 4; ++_) ni *= 2 - ni * mod; return ni; }
u32 n2_dm32(u32 mod) { return mod << 1; }
u32 dmr32(u64 a, u32 ni, u32 n) { u32 y = (u32)(a >> 32) - (u32)(((u64)((u32)a * ni) * n) >> 32); return (i32)y < 0 ? y + n : y; }
u32 to_dm32(u32 a, u32 r2, u32 ni, u32 n) { return dmr32((u64)a * r2, ni, n); }
u32 from_dm32(u32 a, u32 ni, u32 n) { return dmr32((u64)a, ni, n); }
u32 add_dm32(u32 a, u32 b, u32 n) { a += b; a -= (a >= n ? n : 0); return a; }
u32 sub_dm32(u32 a, u32 b, u32 n) { a += (a < b ? n : 0); a -= b; return a; }
u32 min_dm32(u32 a, u32 n) { return sub_dm32(0, a, n); }
u32 relaxed_add_dm32(u32 a, u32 b, u32 n2) { a += b - n2; a += n2 & -(a >> 31u); return a; }
u32 relaxed_sub_dm32(u32 a, u32 b, u32 n2) { a -= b; a += n2 & -(a >> 31u); return a; }
u32 relaxed_min_dm32(u32 a, u32 n2) { return relaxed_sub_dm32(0, a, n2); }
u32 mul_dm32(u32 a, u32 b, u32 ni, u32 n) { return dmr32((u64)a * b, ni, n); }
u32 squ_dm32(u32 a, u32 ni, u32 n) { return dmr32((u64)a * a, ni, n); }
u32 shl_dm32(u32 a, u32 n) { return (a <<= 1) >= n ? a - n : a; }
u32 shr_dm32(u32 a, u32 n) { return (a & 1) ? ((a >> 1) + (n >> 1) + 1) : (a >> 1); }
u32 pow_dm32(u32 a, u64 k, u32 r1, u32 ni, u32 n) { u32 ret = r1; while (k > 0) { if (k & 1) ret = mul_dm32(ret, a, ni, n); a = squ_dm32(a, ni, n); k >>= 1; } return ret; }
u32 inv_dm32(u32 a, u32 r3, u32 ni, u32 n) { return dmr32((u64)r3 * modinv32(a, n), ni, n); }
u32 div_dm32(u32 a, u32 b, u32 r3, u32 ni, u32 n) { return mul_dm32(a, inv_dm32(b, r3, ni, n), ni, n); }
#endif
#if defined(USE_DM64)
u64 r1_dm64(u64 mod) { return (u64)(i64)-1 % mod + 1; }
u64 r2_dm64(u64 mod) { return (u128)(i128)-1 % mod + 1; }
u64 r3_dm64(u64 mod, u64 r1, u64 r2) { return (u64)(((u128)r1 * (u128)r2) % mod); }
u64 n_dm64(u64 mod) { return mod; }
u64 n2_dm64(u64 mod) { return mod << 1; }
u64 ni_dm64(u64 mod) { u64 ni = mod; for (int _ = 0; _ < 5; ++_) ni *= 2 - ni * mod; return ni; }
u64 dmr64(u128 a, u64 ni, u64 n) { u64 y = (u64)(a >> 64) - (u64)(((u128)((u64)a * ni) * n) >> 64); return (i64)y < 0 ? y + n : y; }
u64 to_dm64(u64 a, u64 r2, u64 ni, u64 n) { return dmr64((u128)a * r2, ni, n); }
u64 from_dm64(u64 a, u64 ni, u64 n) { return dmr64((u128)a, ni, n); }
u64 add_dm64(u64 a, u64 b, u64 n) { a += b; a -= (a >= n ? n : 0); return a; }
u64 sub_dm64(u64 a, u64 b, u64 n) { a += (a < b ? n : 0); a -= b; return a; }
u64 min_dm64(u64 a, u64 n) { return sub_dm64(0, a, n); }
u64 relaxed_add_dm64(u64 a, u64 b, u64 n2) { a += b - n2; a += n2 & -(a >> 63u); return a; }
u64 relaxed_sub_dm64(u64 a, u64 b, u64 n2) { a -= b; a += n2 & -(a >> 63u); return a; }
u64 relaxed_min_dm64(u64 a, u64 n2) { return relaxed_sub_dm64(0, a, n2); }
u64 mul_dm64(u64 a, u64 b, u64 ni, u64 n) { return dmr64((u128)a * b, ni, n); }
u64 squ_dm64(u64 a, u64 ni, u64 n) { return dmr64((u128)a * a, ni, n); }
u64 shl_dm64(u64 a, u64 n) { return (a <<= 1) >= n ? a - n : a; }
u64 shr_dm64(u64 a, u64 n) { return (a & 1) ? ((a >> 1) + (n >> 1) + 1) : (a >> 1); }
u64 pow_dm64(u64 a, u64 k, u64 r1, u64 ni, u64 n) { u64 ret = r1; while (k > 0) { if (k & 1) ret = mul_dm64(ret, a, ni, n); a = squ_dm64(a, ni, n); k >>= 1; } return ret; }
u64 inv_dm64(u64 a, u64 r3, u64 ni, u64 n) { return dmr64((u128)r3 * modinv64(a, n), ni, n); }
u64 div_dm64(u64 a, u64 b, u64 r3, u64 ni, u64 n) { return mul_dm64(a, inv_dm64(b, r3, ni, n), ni, n); }
#endif
#if defined(USE_QUADRATIC_RESIDUE)
bool euler_criterion_32(u32 a, u32 mod) {
#if defined(USE_M32)
return pow_m32(to_m32(a), (mod - 1) >> 1) == r1_m32;
#elif defined(USE_B32)
return pow_b32(a, (mod - 1) >> 1) == 1;
#else
u32 ret = 1, b = a, k = (mod - 1) >> 1;
while (k) {
if (k & 1)
ret = (u64)b * ret % mod;
b = (u64)b * b % mod;
k >>= 1;
}
return ret == 1;
#endif
}
bool euler_criterion_64(u64 a, u64 mod) {
#if defined(USE_M64)
return pow_m64(to_m64(a), (mod - 1) >> 1) == r1_m64;
#elif defined(USE_B64)
return pow_b64(a, (mod - 1) >> 1) == 1;
#else
u64 ret = 1, b = a, k = (mod - 1) >> 1;
while (k) {
if (k & 1)
ret = (u128)b * ret % mod;
b = (u128)b * b % mod;
k >>= 1;
}
return ret == 1;
#endif
}
int legendre_symbol_32(u32 a, u32 mod) {
/* assert(a >= 0 && mod & 1 && is_prime(mod)); */
int ret;
#if defined(USE_M32)
if (mr32((u64)a) == 0)
ret = 0;
#else
if (a == 0)
ret = 0;
#endif
else if (euler_criterion_32(a, mod))
ret = 1;
else
ret = -1;
return ret;
}
int legendre_symbol_64(u64 a, u64 mod) {
/* assert(a >= 0 && mod & 1 && is_prime(mod)); */
int ret;
#if defined(USE_M64)
if (mr64((u128)a) == 0)
ret = 0;
#else
if (a == 0)
ret = 0;
#endif
else if (euler_criterion_64(a, mod))
ret = 1;
else
ret = -1;
return ret;
}
int jacobi_symbol(long long a, long long n) {
int j = 1;
long long t;
while (a) {
if (a < 0) {
a = -a;
if ((n & 3) == 3)
j = -j;
}
int s = ctz64(a);
a >>= s;
if ((((n & 7) == 3) || ((n & 7) == 5)) && (s & 1))
j = -j;
if ((a & n & 3) == 3)
j = -j;
t = a, a = n, n = t;
a %= n;
if ((a << 1) > n)
a -= n;
}
return n == 1 ? j : 0;
}
#endif
static const u32 base32[256] = {
1216, 1836, 8885, 4564, 10978, 5228, 15613, 13941,
1553, 173, 3615, 3144, 10065, 9259, 233, 2362,
6244, 6431, 10863, 5920, 6408, 6841, 22124, 2290,
45597, 6935, 4835, 7652, 1051, 445, 5807, 842,
1534, 22140, 1282, 1733, 347, 6311, 14081, 11157,
186, 703, 9862, 15490, 1720, 17816, 10433, 49185,
2535, 9158, 2143, 2840, 664, 29074, 24924, 1035,
41482, 1065, 10189, 8417, 130, 4551, 5159, 48886,
786, 1938, 1013, 2139, 7171, 2143, 16873, 188,
5555, 42007, 1045, 3891, 2853, 23642, 148, 3585,
3027, 280, 3101, 9918, 6452, 2716, 855, 990,
1925, 13557, 1063, 6916, 4965, 4380, 587, 3214,
1808, 1036, 6356, 8191, 6783, 14424, 6929, 1002,
840, 422, 44215, 7753, 5799, 3415, 231, 2013,
8895, 2081, 883, 3855, 5577, 876, 3574, 1925,
1192, 865, 7376, 12254, 5952, 2516, 20463, 186,
5411, 35353, 50898, 1084, 2127, 4305, 115, 7821,
1265, 16169, 1705, 1857, 24938, 220, 3650, 1057,
482, 1690, 2718, 4309, 7496, 1515, 7972, 3763,
10954, 2817, 3430, 1423, 714, 6734, 328, 2581,
2580, 10047, 2797, 155, 5951, 3817, 54850, 2173,
1318, 246, 1807, 2958, 2697, 337, 4871, 2439,
736, 37112, 1226, 527, 7531, 5418, 7242, 2421,
16135, 7015, 8432, 2605, 5638, 5161, 11515, 14949,
748, 5003, 9048, 4679, 1915, 7652, 9657, 660,
3054, 15469, 2910, 775, 14106, 1749, 136, 2673,
61814, 5633, 1244, 2567, 4989, 1637, 1273, 11423,
7974, 7509, 6061, 531, 6608, 1088, 1627, 160,
6416, 11350, 921, 306, 18117, 1238, 463, 1722,
996, 3866, 6576, 6055, 130, 24080, 7331, 3922,
8632, 2706, 24108, 32374, 4237, 15302, 287, 2296,
1220, 20922, 3350, 2089, 562, 11745, 163, 11951};
bool is_prime_m32(u32 n) {
set_m32(n);
u32 b = base32[(u32)(n * 2908904329) >> 24];
u32 s = ctz32(n - 1);
u32 d = (n - 1) >> s;
u32 a = to_m32(b);
u32 c = pow_m32(a, d);
if (c == r1_m32)
return true;
for (u32 r = 0; r < s; r++) {
if (c == n - r1_m32)
return true;
c = squ_m32(c);
}
return false;
}
bool is_prime_b32(u32 n) {
set_b32(n);
u32 b = base32[(u32)(n * 2908904329) >> 24];
u32 s = ctz32(n - 1);
u32 d = (n - 1) >> s;
u32 c = pow_b32(b, d);
if (c == 1)
return true;
for (u32 r = 0; r < s; r++) {
if (c == n - 1)
return true;
c = squ_b32(c);
}
return false;
}
bool is_prime_m64(u64 n) {
set_m64(n);
{
u64 d = (n - 1) << clz64(n - 1);
u64 t = shl_m64(r1_m64);
for (d <<= 1; d; d <<= 1) {
t = squ_m64(t);
if (d >> 63)
t = shl_m64(t);
}
if (t != r1_m64) {
u64 x = only_lsb(n - 1);
u64 r = n - r1_m64;
for (x >>= 1; t != r; x >>= 1) {
if (x == 0)
return false;
t = squ_m64(t);
}
}
}
i64 D = 5;
{
for (int i = 0; jacobi_symbol(D, n) != -1 && i < 64; ++i) {
if (i == 32) {
u64 sqrt_n = (u64)sqrtl((long double)n);
if (n == sqrt_n * sqrt_n)
return false;
}
D = i & 1 ? 2 - D : -2 - D;
}
}
u64 Q, Qn, u, v, k;
{
Q = to_m64((D < 0) ? ((1 - D) / 4 % n) : (n - (D - 1) / 4 % n));
Qn = Q;
u = r1_m64;
v = r1_m64;
k = (n + 1) << clz64(n + 1);
D %= (i64)n;
D = to_m64((D < 0) ? (D + n) : D);
}
{
for (k <<= 1; k; k <<= 1) {
u = mul_m64(u, v);
v = sub_m64(squ_m64(v), add_m64(Qn, Qn));
Qn = squ_m64(Qn);
if (k >> 63) {
u64 uu = add_m64(u, v);
uu = shr_m64(uu);
v = shr_m64(add_m64(mul_m64(D, u), v));
u = uu;
Qn = mul_m64(Qn, Q);
}
}
if (u == 0 || v == 0)
return true;
u64 x = (n + 1) & ~n;
for (x >>= 1; x; x >>= 1) {
u = mul_m64(u, v);
v = sub_m64(squ_m64(v), add_m64(Qn, Qn));
if (v == 0)
return true;
Qn = squ_m64(Qn);
}
}
return false;
}
bool is_prime_b64(u64 n) {
set_b64(n);
{
u64 d = (n - 1) << clz64(n - 1);
u64 t = 2ull;
for (d <<= 1; d; d <<= 1) {
t = squ_b64(t);
if (d >> 63)
t = shl_b64(t);
}
if (t != 1ull) {
u64 x = only_lsb(n - 1);
u64 r = n - 1;
for (x >>= 1; t != r; x >>= 1) {
if (x == 0)
return false;
t = squ_b64(t);
}
}
}
i64 D = 5;
{
for (int i = 0; jacobi_symbol(D, n) != -1 && i < 64; ++i) {
if (i == 32) {
u64 sqrt_n = (u64)sqrtl((long double)n);
if (n == sqrt_n * sqrt_n)
return false;
}
D = i & 1 ? 2 - D : -2 - D;
}
}
u64 Q, Qn, u, v, k;
{
Q = ((D < 0) ? ((1 - D) / 4 % n) : (n - (D - 1) / 4 % n));
Qn = Q;
u = 1ull;
v = 1ull;
k = (n + 1) << clz64(n + 1);
D %= (i64)n;
D = ((D < 0) ? (D + n) : D);
}
{
for (k <<= 1; k; k <<= 1) {
u = mul_b64(u, v);
v = sub_b64(squ_b64(v), add_b64(Qn, Qn));
Qn = squ_b64(Qn);
if (k >> 63) {
u64 uu = add_b64(u, v);
uu = shr_b64(uu);
v = shr_b64(add_b64(mul_b64(D, u), v));
u = uu;
Qn = mul_b64(Qn, Q);
}
}
if (u == 0 || v == 0)
return true;
u64 x = (n + 1) & ~n;
for (x >>= 1; x; x >>= 1) {
u = mul_b64(u, v);
v = sub_b64(squ_b64(v), add_b64(Qn, Qn));
if (v == 0)
return true;
Qn = squ_b64(Qn);
}
}
return false;
}
bool is_prime(u64 n) {
if (n < 64ull)
return (1ull << n) & 2891462833508853932ull;
if (!(n & 1))
return false;
if (gcd64(n, 15) != 1ull)
return false;
if (gcd64(n, 77) != 1ull)
return false;
if (n < 121ull)
return true;
if (n < 1073741824)
return is_prime_m32((u32)n);
if (n < 4294967296ull)
return is_prime_b32((u32)n);
if (n < 4611686018427387904ull)
return is_prime_m64(n);
return is_prime_b64(n);
}
int main(void) {
u32 Q;
rd_u32(&Q);
while (Q--) {
u64 n;
rd_u64(&n);
wt_u64(n);
wt_sp();
wt_str(is_prime(n) ? "1\n" : "0\n");
}
return 0;
}