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

• 問題: No.3030 ミラー・ラビン素数判定法のテスト
• ユーザー: Jashinchan
• 提出日時: 2022-09-02 21:34:39
• 言語: C (gcc 12.3.0)
• 結果: AC
• 実行時間: 20 ms / 9,973 ms
• コード長: 9,318 bytes
• コンパイル時間: 534 ms
• コンパイル使用メモリ: 45,280 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-11-17 00:05:27
• 合計ジャッジ時間: 1,212 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	AC	1 ms; 5,248 KB
testcase_04	AC	14 ms; 5,248 KB
testcase_05	AC	18 ms; 5,248 KB
testcase_06	AC	16 ms; 5,248 KB
testcase_07	AC	16 ms; 5,248 KB
testcase_08	AC	16 ms; 5,248 KB
testcase_09	AC	20 ms; 5,248 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;
}