結果
| 問題 | No.3030 ミラー・ラビン素数判定法のテスト |
| ユーザー |
 Jashinchan
|
| 提出日時 | 2022-09-02 21:34:39 |
| 言語 | C (gcc 12.3.0) |
| 結果 |
AC
|
| 実行時間 | 18 ms / 9,973 ms |
| コード長 | 9,318 bytes |
| コンパイル時間 | 512 ms |
| コンパイル使用メモリ | 44,920 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-04-28 10:06:00 |
| 合計ジャッジ時間 | 1,042 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 0 ms
5,248 KB |
| testcase_01 | AC | 1 ms
5,376 KB |
| testcase_02 | AC | 1 ms
5,376 KB |
| testcase_03 | AC | 0 ms
5,376 KB |
| testcase_04 | AC | 12 ms
5,376 KB |
| testcase_05 | AC | 16 ms
5,376 KB |
| testcase_06 | AC | 15 ms
5,376 KB |
| testcase_07 | AC | 15 ms
5,376 KB |
| testcase_08 | AC | 15 ms
5,376 KB |
| testcase_09 | AC | 18 ms
5,376 KB |
ソースコード
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#define _GNU_SOURCE
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <math.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;
typedef float f32;
typedef double f64;
typedef long double f80;
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define SWAP_REF(a, b) \
do { \
(a) ^= (b); \
(b) ^= (a); \
(a) ^= (b); \
} \
while(0);
#define CTZ32(a) ((a) ? __builtin_ctz((a)) : (32))
#define CTZ64(a) ((a) ? __builtin_ctzll((a)) : (64))
#define CLZ32(a) ((a) ? __builtin_clz((a)) : (32))
#define CLZ64(a) ((a) ? __builtin_clzll((a)) : (64))
#define POPCNT32(a) ((a) ? __builtin_popcount((a)) : (0))
#define POPCNT64(a) ((a) ? __builtin_popcountll((a)) : (0))
#define MSB32(a) ((a) ? ((31) - __builtin_clz((a))) : (-1))
#define MSB64(a) ((a) ? ((63) - __builtin_clzll((a))) : (-1))
#define LSBit(a) ((a) & (-(a)))
#define CLSBit(a) ((a) & ((a) - (1)))
#define _ROTL32_INNER(x, l) (((x) << (l)) | ((x) >> ((-l) & (31))))
#define _ROTR32_INNER(x, r) (((x) >> (r)) | ((x) << ((-r) & (31))))
#define _ROTL64_INNER(x, l) (((x) << (l)) | ((x) >> ((-l) & (63))))
#define _ROTR64_INNER(x, r) (((x) >> (r)) | ((x) << ((-r) & (63))))
#define ROTR32(x, r) (((r) < (0)) ? \
(_ROTL32_INNER((x), ((u64)(-r) % (32)))) : \
(_ROTR32_INNER((x), ((r) % (32)))))
#define ROTL32(x, l) ROTR32((x), (-l))
#define ROTR64(x, r) (((r) < (0)) ? \
(_ROTL64_INNER((x), ((u64)(-r) % (64)))) : \
(_ROTR64_INNER((x), ((r) % (64)))))
#define ROTL64(x, l) ROTR64((x), (-l))
#define BIT_FLOOR32(a) ((a) ? (1u) << MSB32((a)) : (0))
#define BIT_FLOOR64(a) ((a) ? (1ull) << MSB64((a)) : (0))
#define BIT_CEIL32_REF(a) \
do { \
--(a); \
(a) |= (a) >> (1); \
(a) |= (a) >> (2); \
(a) |= (a) >> (4); \
(a) |= (a) >> (8); \
(a) |= (a) >> (16); \
(a)++; \
} while(0);
#define BIT_CEIL64_REF(a) \
do { \
--(a); \
(a) |= (a) >> (1); \
(a) |= (a) >> (2); \
(a) |= (a) >> (4); \
(a) |= (a) >> (8); \
(a) |= (a) >> (16); \
(a) |= (a) >> (32); \
(a)++; \
} while(0);
u64 in(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;
}
void out(u64 x)
{
if (x >= 10) out((((u128)x * 14757395258967641293ull) >> 3) >> 64);
putchar_unlocked(x - ((((u128)x * 14757395258967641293ull) >> 3) >> 64) * 10 + 48);
}
//-----------------------------------------------------------------------------
// util.c
//-----------------------------------------------------------------------------
u64 gcd64(u64 a, u64 b)
{
if (!a || !b) return a | b;
u64 sh = __builtin_ctzll(a | b);
a >>= __builtin_ctzll(a);
do {
b >>= __builtin_ctzll(b);
if (a > b) SWAP_REF(a, b);
b -= a;
} while (b);
return a << sh;
}
int jacobi_symbol(i64 a, u64 n)
{
int j = 1;
while (a)
{
if (a < 0)
{
a = -a;
if ((n & 3) == 3) { j = -j; }
}
int s = __builtin_ctzll(a);
a >>= s;
if (((n & 7) == 3 || (n & 7) == 5) && (s & 1)) { j = -j; }
if ((a & n & 3) == 3) { j = -j; }
SWAP_REF(a, n);
a %= n;
if ((u64)(a) > n / 2) { a -= n; }
}
return n == 1 ? j : 0;
}
//-----------------------------------------------------------------------------
// primality_test.c
//-----------------------------------------------------------------------------
u64 mr64(u128 a, u64 n, u64 ni)
{
u64 y = (u64)(a >> 64) - (u64)(((u128)((u64)a * ni) * n) >> 64);
return (i64)y < 0 ? y + n : y;
}
u64 add_m64(u64 a, u64 b, u64 n)
{
a += b;
a -= (a >= n ? n : 0);
return a;
}
u64 sub_m64(u64 a, u64 b, u64 n)
{
a += (a < b ? n : 0);
a -= b;
return a;
}
u64 mul_m64(u64 a, u64 b, u64 n, u64 ni)
{
return mr64((u128)a * b, n, ni);
}
u64 sqr_m64(u64 a, u64 n, u64 ni)
{
return mr64((u128)a * a, n, ni);
}
u64 pow_m64(u64 a, u64 k, u64 n, u64 ni, u64 r)
{
u64 ret = r, A = a, deg = k;
while (deg > 0)
{
if (deg & 1) { ret = mul_m64(ret, A, n, ni); }
A = mul_m64(A, A, n, ni);
deg >>= 1;
}
return ret;
}
u64 twi_m64(u64 a, u64 n)
{
return (a <<= 1) >= n ? a - n : a;
}
u64 half_m64(u64 a, u64 n)
{
return (a & 1) ? ((a >> 1) + (n >> 1) + 1) : (a >> 1);
}
int is_prime(u64 n)
{
{
if (n < 2)
return 0;
if (n < 4)
return 1;
if (!(n & 1))
return 0;
}
if (n < 1000)
{
if (n % 3 == 0)
return 0;
for (int i = 5; i * i <= n; i += 6)
{
if (n % i == 0 || n % (i + 2) == 0)
return 0;
}
return 1;
}
if (gcd64(15ull, n) != 1ull)
{
return 0;
}
u64 r = (u64)(i64)-1 % n + 1;
u64 r2 = (u128)(i128)-1 % n + 1;
u64 ni = n;
ni *= 2 - ni * n;
ni *= 2 - ni * n;
ni *= 2 - ni * n;
ni *= 2 - ni * n;
ni *= 2 - ni * n;
u64 two = mr64((u128)r2 * 2, n, ni);
u64 rev = mr64((u128)r2 * (n - 1), n, ni);
{
u64 lhs = pow_m64(two, (n - 1) / 2, n, ni, r);
if (lhs != r && lhs != rev)
return 0;
}
if (n < 4294967296ull)
{
u64 bases[] = { 2ull, 7ull, 61ull };
int s = __builtin_ctzll(n - 1);
u64 d = (n - 1) >> s;
for (int i = 0; i < 3; ++i)
{
if (bases[i] >= n) break;
u64 a = mr64((u128)r2 * bases[i], n, ni);
u64 c = pow_m64(a, d, n, ni, r);
if (c == r) continue;
int f = 0;
for (int q = 0; q < s && f == 0; ++q)
{
f |= (c == rev);
c = sqr_m64(c, n, ni);
}
if (f == 0) return 0;
}
return 1;
}
{
u64 a = 4294967296ull;
u64 A = mr64((u128)r2 * a, n, ni);
int x = jacobi_symbol(a, n);
u64 y = (x == -1) ? rev : (x == 0 ? 0 : r);
if (y == 0 || y != pow_m64(A, (n - 1) / 2, n, ni, r))
return 0;
}
// {
// u64 d = (n - 1) << __builtin_clzll(n - 1);
// u64 t = two;
// for (d <<= 1; d; d <<= 1)
// {
// t = sqr_m64(t, n, ni);
// if (d >> 63) t = twi_m64(t, n);
// }
// if (t != r)
// {
// u64 x = LSBit(n - 1);
// for (x >>= 1; t != rev; x >>= 1)
// {
// if (x == 0) return 0;
// t = sqr_m64(t, n, ni);
// }
// }
// }
{
i64 D = 5;
for (int i = 0; jacobi_symbol(D, n) != -1 && i < 64; ++i)
{
if (i == 32)
{
u64 k = round(sqrtl(n));
if (k * k == n) return 0;
}
if (i & 1) D -= 2;
else D += 2;
D = -D;
}
u64 Q = mr64((u128)r2 * ((D < 0) ?
((1 - D) / 4 % n) :
(n - (D - 1) / 4 % n)), n, ni);
u64 u = r, v = r, Qn = Q;
u64 k = (n + 1) << __builtin_clzll(n + 1);
D %= (i64)n;
D = mr64((u128)r2 * ((D < 0) ? ((i64)n + D) : D), n, ni);
for (k <<= 1; k; k <<= 1) {
u = mul_m64(u, v, n, ni);
v = sub_m64(sqr_m64(v, n, ni), add_m64(Qn, Qn, n), n);
Qn = sqr_m64(Qn, n, ni);
if (k >> 63) {
u64 uu = add_m64(u, v, n);
uu = half_m64(uu, n);
v = add_m64(mul_m64(D, u, n, ni), v, n);
v = half_m64(v, n);
u = uu;
Qn = mul_m64(Qn, Q, n, ni);
}
}
if (u == 0 || v == 0) return 1;
u64 x = (n + 1) & ~n;
for (x >>= 1; x; x >>= 1)
{
u = mul_m64(u, v, n, ni);
v = sub_m64(sqr_m64(v, n, ni), add_m64(Qn, Qn, n), n);
if (v == 0) return 1;
Qn = sqr_m64(Qn, n, ni);
}
}
return 0;
}
int main(void)
{
u64 T = in();
while (T--) {
u64 x = in();
out(x);
putchar_unlocked(' ');
out(is_prime(x));
putchar_unlocked('\n');
}
return 0;
}