#796913 (C) No.3030 ミラー・ラビン素数判定法のテスト

提出ソース
結果

問題	No.3030 ミラー・ラビン素数判定法のテスト
ユーザー	Jashinchan
提出日時	2022-09-13 22:06:23
言語	C (gcc 12.3.0)
結果	AC
実行時間	17 ms / 9,973 ms
コード長	13,416 bytes
コンパイル時間	2,576 ms
コンパイル使用メモリ	47,192 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-12-14 06:17:35
合計ジャッジ時間	3,265 ms
ジャッジサーバーID （参考情報）	judge1 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,820 KB
testcase_01	AC	1 ms 6,820 KB
testcase_02	AC	1 ms 6,816 KB
testcase_03	AC	1 ms 6,816 KB
testcase_04	AC	10 ms 6,816 KB
testcase_05	AC	13 ms 6,816 KB
testcase_06	AC	11 ms 6,820 KB
testcase_07	AC	10 ms 6,816 KB
testcase_08	AC	11 ms 6,816 KB
testcase_09	AC	17 ms 6,816 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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

int jacobi_symbol(i64 a, u64 n) {
    u64 t;
    int j = 1;
    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 ((u64)(a) > n / 2)
            a -= n;
    }
    return n == 1 ? j : 0;
}

bool is_square(u64 N)
{
    if (N <= 1)
        return true;
    if ((0x02030213u >> ((u32)N & 31)) & 1 != 1)
        return false;
    const u64 SQTABLE_MOD4095[64] =
    {
        0x2001002010213ul,    0x4200001008028001ul, 0x20000010004ul,      0x80200082010ul,
        0x1800008200044029ul, 0x120080000010ul,     0x2200000080410400ul, 0x8100041000200800ul,
        0x800004000020100ul,  0x402000400082201ul,  0x9004000040ul,       0x800002000880ul,
        0x18002000012000ul,   0x801208ul,           0x26100000804010ul,   0x80000080000002ul,
        0x108040040101045ul,  0x20c00004000102ul,   0x400000100c0010ul,   0x1300000040208ul,
        0x804000020010000ul,  0x1008402002400080ul, 0x201001000200040ul,  0x4402000000806000ul,
        0x10402000000ul,      0x1040008001200801ul, 0x4080000000020400ul, 0x10083080000002ul,
        0x8220140000040000ul, 0x800084020100000ul,  0x80010400010000ul,   0x1200020108008060ul,
        0x180000000ul,        0x400002400000018ul,  0x4241000200ul,       0x100800000000ul,
        0x10201008400483ul,   0xc008000208201000ul, 0x800420000100ul,     0x2010002000410ul,
        0x28041000000ul,      0x4010080000024ul,    0x400480010010080ul,  0x200040028000008ul,
        0x100810084020ul,     0x20c0401000080000ul, 0x1000240000220000ul, 0x4000020800ul,
        0x410000000480000ul,  0x8004008000804201ul, 0x806020000104000ul,  0x2080002000211000ul,
        0x1001008001000ul,    0x20000010024000ul,   0x480200002040000ul,  0x48200044008000ul,
        0x100000000010080ul,  0x80090400042ul,      0x41040200800200ul,   0x4000020100110ul,
        0x2000400082200010ul, 0x1008200000000040ul, 0x2004800002ul,       0x2002010000080ul
    };
    size_t p = N % 4095;
    if ((SQTABLE_MOD4095[p >> 6] >> (p & 63)) & 1 != 1)
        return false;
    u64 newton_sqrt;
    size_t k = 32 - (CLZ64(N - 1) >> 1);
    u64 s = (u64)(1ul) << k;
    u64 t = (s + (N >> k)) >> 1;
    while (t < s)
    {
        s = t;
        t = (s + N / s) >> 1;
    }
    newton_sqrt = s;
    if (newton_sqrt * newton_sqrt != N)
        return false;
    return true;
}

/******************************/
/* 64bit montgomery reduction */
/******************************/
static u64 N = 0ul, NI = 0ul, R1 = 0ul, R2 = 0ul;
void Montgomery64(u64 n)
{
    N = n;
    NI = n;
    for (int _ = 0; _ < 5; ++_)
    {
        NI *= 2 - NI * n;
    }
    R1 = (u64)(i64)-1 % n + 1;
    R2 = (u128)(i128)-1 % n + 1;
}
u64 mr64(u128 A) { u64 y = (u64)(A >> 64) - (u64)(((u128)((u64)A * NI) * N) >> 64); return (i64)y < 0 ? y + N : y; }
u64 To(u64 a) { return mr64((u128)R2 * a); }
u64 From(u64 mra) { return mr64((u128)mra); }
u64 Add(u64 mra, u64 mrb) { mra += mrb; mra -= (mra >= N ? N : 0); return mra; }
u64 Sub(u64 mra, u64 mrb) { mra += (mra < mrb ? N : 0); mra -= mrb; return mra; }
u64 Min(u64 mra) { return Sub(0, mra); }
u64 Mul(u64 mra, u64 mrb) { return mr64((u128)mra * mrb); }
u64 Square(u64 mra) { return mr64((u128)mra * mra); }
u64 Twice(u64 mra) { return (mra <<= 1) >= N ? (mra - N) : mra; }
u64 Power(u64 mra, u64 k) { u64 ret = R1, a = mra; while (k > 0) { if (k & 1) { ret = Mul(ret, a); } a = Mul(a, a); k >>= 1; } return ret; }
u64 Inverse(u64 mra) { return Power(mra, N - 2); }
u64 Div(u64 mra, u64 mrb) { return Mul(mra, Inverse(mrb)); }
u64 Half(u64 mra) { return (mra & 1) ? ((mra >> 1) + (N >> 1) + 1) : (mra >> 1); }
int Equal(u64 mra, u64 mrb) { return (((mra >= N) ? (mra - N) : mra) == ((mrb >= N) ? (mrb - N) : mrb)) ? 1 : 0; }
int NotEqual(u64 mra, u64 mrb) { return (((mra >= N) ? (mra - N) : mra) != ((mrb >= N) ? (mrb - N) : mrb)) ? 1 : 0; }
u64 In() { u64 c = 0; u64 a = 0; while (c = getchar_unlocked(), c < 48 || c > 57); while (47 < c && c < 58) { a = a * 10 + c - 48; c = getchar_unlocked(); } return To(a); }
void Out(u64 mra) { u64 a = From(mra); out_u64(a); }

bool baillie_psw(u64 n)
{
    {
        if (n < 2) return false;
        if (n < 4) return true;
        if (!(n & 1)) return false;
        if (n % 3 == 0) return false;
    }
    Montgomery64(n);
    {
        u64 d = (n - 1) << CLZ64(n - 1);
        u64 t = Twice(R1);
        for (d <<= 1; d; d <<= 1)
        {
            t = Square(t);
            if (d >> 63) t = Twice(t);
        }
        if (t != R1)
        {
            u64 x = LSBit(n - 1);
            u64 rev = Min(R1);
            for (x >>= 1; t != rev; x >>= 1)
            {
                if (x == 0) return false;
                t = Square(t);
            }
        }
    }
    {
        i64 D = 5;
        for (int i = 0; jacobi_symbol(D, n) != -1 && i < 64; ++i)
        {
            if (i == 32 && is_square(n) == 0) return false;
            if (i & 1) D -= 2;
            else       D += 2;
            D = -D;
        }
        u64 Q = To((D < 0) ? ((1 - D) / 4 % n) : (n - (D - 1) / 4 % n));
        u64 u = R1, v = R1, Qn = Q;
        u64 k = (n + 1) << CLZ64(n + 1);
        D %= (i64)n;
        D = To((D < 0) ? (D + n) : D);
        for (k <<= 1; k; k <<= 1)
        {
            u = Mul(u, v);
            v = Sub(Square(v), Add(Qn, Qn));
            Qn = Square(Qn);
            if (k >> 63)
            {
                u64 uu = Add(u, v);
                uu = Half(uu);
                v = Half(Add(Mul(D, u), v));
                u = uu;
                Qn = Mul(Qn, Q);
            }
        }
        if (u == 0 || v == 0) return true;
        u64 x = (n + 1) & ~n;
        for (x >>= 1; x; x >>= 1)
        {
            u = Mul(u, v);
            v = Sub(Square(v), Add(Qn, Qn));
            if (v == 0) return true;
            Qn = Square(Qn);
        }
    }
    return false;
}

int main(void)
{
    int Q = in_i32();
    while (Q--)
    {
        u64 x = in_u64();
        out_u64(x);
        SP();
        out_i32(baillie_psw(x));
        NL();
    }
    return 0;
}
yukicoder

結果

テストケース

ソースコード
