結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー JashinchanJashinchan
提出日時 2022-09-13 17:57:02
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 60 ms / 9,973 ms
コード長 10,738 bytes
コンパイル時間 844 ms
コンパイル使用メモリ 45,416 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-05-08 01:59:24
合計ジャッジ時間 1,632 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 0 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 36 ms
5,376 KB
testcase_05 AC 35 ms
5,376 KB
testcase_06 AC 18 ms
5,376 KB
testcase_07 AC 18 ms
5,376 KB
testcase_08 AC 18 ms
5,376 KB
testcase_09 AC 60 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")

#define _GNU_SOURCE
#include <assert.h>
#include <inttypes.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 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   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);

i32 in_i32(void) { i32 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 void out_i32_inner(i32 x) { if (x >= 10) out_i32_inner(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); }
void out_i32(i32 x) { if (x < 0) { putchar_unlocked('-'); x = -x; } out_i32_inner(x); }
i64 in_i64(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 void out_i64_inner(i64 x) { if (x >= 10) out_i64_inner(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); }
void out_i64(i64 x) { if (x < 0) { putchar_unlocked('-'); x = -x; } out_i64_inner(x); }
u32 in_u32(void) { u32 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_u32(u32 x) { if (x >= 10) out_u32(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); }
u64 in_u64(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(u64 x) { if (x >= 10) out_u64(x / 10); putchar_unlocked(x - x / 10 * 10 + 48); }
void NL(void) { putchar_unlocked('\n'); }
void SP(void) { putchar_unlocked(' '); }

void dump_i32(i32 x) { fprintf(stderr, "\033[1;36m%" PRId32 "\033[0m\n", x); }
void dump_i64(i64 x) { fprintf(stderr, "\033[1;36m%" PRId64 "\033[0m\n", x); }
void dump_u32(u32 x) { fprintf(stderr, "\033[1;36m%" PRIu32 "\033[0m\n", x); }
void dump_u64(u64 x) { fprintf(stderr, "\033[1;36m%" PRIu64 "\033[0m\n", x); }
void dump_i32_array(i32 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i == a_len - 1) { fprintf(stderr, "\033[1;36m%" PRId32 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRId32 "\033[0m ", a[i]); } } }
void dump_i64_array(i64 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i == a_len - 1) { fprintf(stderr, "\033[1;36m%" PRId64 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRId64 "\033[0m ", a[i]); } } }
void dump_u32_array(u32 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i == a_len - 1) { fprintf(stderr, "\033[1;36m%" PRIu32 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRIu32 "\033[0m ", a[i]); } } }
void dump_u64_array(u64 *a, int a_len) { for (int i = 0; i < a_len; i++) { if (i == a_len - 1) { fprintf(stderr, "\033[1;36m%" PRIu64 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRIu64 "\033[0m ", a[i]); } } }
void dump_i32_array_range(i32 *a, int a_len, int l, int r) { if (a_len <= r) { r = a_len - 1; } if (l > r) { return; } for (int i = l; i <= r; i++) { if (i == r) { fprintf(stderr, "\033[1;36m%" PRId32 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRId32 "\033[0m ", a[i]); } } }
void dump_i64_array_range(i64 *a, int a_len, int l, int r) { if (a_len <= r) { r = a_len - 1; } if (l > r) { return; } for (int i = l; i <= r; i++) { if (i == r) { fprintf(stderr, "\033[1;36m%" PRId64 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRId64 "\033[0m ", a[i]); } } }
void dump_u32_array_range(u32 *a, int a_len, int l, int r) { if (a_len <= r) { r = a_len - 1; } if (l > r) { return; } for (int i = l; i <= r; i++) { if (i == r) { fprintf(stderr, "\033[1;36m%" PRIu32 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRIu32 "\033[0m ", a[i]); } } }
void dump_u64_array_range(u64 *a, int a_len, int l, int r) { if (a_len <= r) { r = a_len - 1; } if (l > r) { return; } for (int i = l; i <= r; i++) { if (i == r) { fprintf(stderr, "\033[1;36m%" PRIu64 "\033[0m\n", a[i]); } else { fprintf(stderr, "\033[1;36m%" PRIu64 "\033[0m ", a[i]); } } }
void printb_32bit(u32 v) { u32 mask = (u32)1 << (sizeof(v) * CHAR_BIT - 1); do { putchar_unlocked(mask & v ? '1' : '0'); } while (mask >>= 1); }
void printb_64bit(u64 v) { u64 mask = (u64)1 << (sizeof(v) * CHAR_BIT - 1); do { putchar_unlocked(mask & v ? '1' : '0'); } while (mask >>= 1); }
// clang-format on


/***************************/
/* 64bit barrett reduction */
/***************************/
u64 m_b64;
u64 im_b64;
u64 divrem64[2] = {0};
void new_br64(u64 m)
{
    m_b64 = m;
    im_b64 = (~((u64)0ul)) / m;
}
void div_rem_b64(u64 lhs)
{
    if (m_b64 == 1)
    {
        divrem64[0] = lhs;
        divrem64[1] = 0;
    }
    u64 q = (u64)(((u128)lhs * (u128)im_b64) >> 64);
    u64 r = lhs - q * m_b64;
    if (m_b64 <= r)
    {
        r -= m_b64;
        q += 1ul;
    }
    divrem64[0] = q;
    divrem64[1] = r;
}
u32 mul_br32(u32 a, u32 b)
{
    div_rem_b64((u64)a * b);
    return divrem64[1];
}
u32 pow_br32(u32 a, u32 k)
{
    u32 ret = 1u;
    while (k > 0)
    {
        if (k & 1)
            ret = mul_br32(ret, a);
        a = mul_br32(a, a);
        k >>= 1;
    }
    return ret;
}


/****************************/
/* 128bit barrett reduction */
/****************************/
u128 m_b128;
u128 im_b128;
u128 divrem128[2] = {0};
void new_br128(u128 m)
{
    m_b128 = m;
    im_b128 = (~((u128)0ull)) / m;
}
void div_rem_b128(u128 lhs)
{
    u128 t = (lhs >> 64) * (im_b128 >> 64);
    u128 x = ((lhs & 0xffffffffffffffffull) * (im_b128 & 0xffffffffffffffffull)) >> 64;
    u8 flag;
    u128 auil = (lhs >> 64) * (im_b128 & 0xffffffffffffffffull);
    if (auil <= (u128)((i128)(-1L)) - x) flag = 0;
    else flag = 1;
    x += auil;
    t += flag;
    u128 aliu = (lhs & 0xffffffffffffffffull) * (im_b128 >> 64);
    if (aliu <= (u128)((i128)(-1L)) - x) flag = 0;
    else flag = 1;
    x += aliu;
    t += flag;
    u128 q = t + (x >> 64);
    u128 r = lhs - q * m_b128;
    if (m_b128 <= r)
    {
        r -= m_b128;
        q += 1;
    }
    divrem128[0] = q;
    divrem128[1] = r;
}
u64 mul_br64(u64 a, u64 b)
{
    div_rem_b128((u128)a * b);
    return (u64)divrem128[1];
}
u64 pow_br64(u64 a, u64 k)
{
    u64 ret = 1ul;
    while (k > 0)
    {
        if (k & 1)
            ret = mul_br64(ret, a);
        a = mul_br64(a, a);
        k >>= 1;
    }
    return ret;
}


/******************************************************/
/* Miller Rabin Primality Test with Barrett Reduction */
/******************************************************/
bool miller_rabin_br32(u32 N)
{
    const u32 bases[3] = {2u, 7u, 61u};
    new_br64((u64)N);
    u32 d = (N - 1) >> CTZ32(N - 1);
    for (int i = 0; i < 3; ++i)
    {
        if (N <= bases[i]) break;
        u32 tt = d;
        u32 y = pow_br32(bases[i], tt);
        while (tt != N - 1 && y != 1 && y != N - 1)
        {
            y = mul_br32(y, y);
            tt <<= 1;
        }
        if (y != N - 1 && (~tt & 1)) return false;
    }
    return true;
}
bool miller_rabin_br64(u64 N)
{
    const u64 bases[7] = {2ul, 325ul, 9375ul, 28178ul, 450775ul, 9780504ul, 1795265022ul};
    new_br128((u128)N);
    u64 d = (N - 1) >> CTZ64(N - 1);
    for (int i = 0; i < 7; ++i)
    {
        if (N <= bases[i]) break;
        u64 tt = d;
        u64 y = pow_br64(bases[i], tt);
        while (tt != N - 1 && y != 1 && y != N - 1)
        {
            y = mul_br64(y, y);
            tt <<= 1;
        }
        if (y != N - 1 && (~tt & 1)) return false;
    }
    return true;
}

bool is_prime(u64 N)
{
    if (N < 2) return false;
    if (~N & 1) return N == 2;
    if (N % 3 == 0) return N == 3;

    if (N < 4294967296ul)
        return miller_rabin_br32((u32)N);
    else
        return miller_rabin_br64(N);
}

int main(void)
{
    int Q;
    scanf("%d", &Q);
    while (Q--)
    {
        u64 x;
        scanf("%" PRIu64, &x);
        printf("%" PRIu64 " ", x);
        printf("%d\n", is_prime(x));
    }
    return 0;
}
0