結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー Jashinchan
提出日時 2022-08-27 19:41:42
言語 C
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 5,062 bytes
コンパイル時間 1,079 ms
コンパイル使用メモリ 35,416 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-14 16:10:52
合計ジャッジ時間 1,669 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 6
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'in_u128':
main.c:128:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration]
  128 |     char c = getchar_unlocked();
      |              ^~~~~~~~~~~~~~~~
main.c: In function 'out_u128':
main.c:143:5: warning: implicit declaration of function 'putchar_unlocked' [-Wimplicit-function-declaration]
  143 |     putchar_unlocked(x % 10 + '0');
      |     ^~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <stdint.h>
#include <stdio.h>

typedef int64_t i64;
typedef uint64_t u64;
typedef __int128_t i128;
typedef __uint128_t u128;


typedef struct {
    u128 lo, hi;
} u256;

typedef struct {
    u256 lo, hi;
} u512;

u256 make_u256(u128 lo, u128 hi)
{
    u256 ret;
    ret.lo = lo;
    ret.hi = hi;
    return ret;
}

u512 make_u512(u256 lo, u256 hi)
{
    u512 ret;
    ret.lo = lo;
    ret.hi = hi;
    return ret;
}

const u128 MSB128 = ((u128)0x8000000000000000ull) << 64;

u256 mul128(u128 a, u128 b)
{
    u64 a_hi = a >> 64, a_lo = (u64)a;
    u64 b_hi = b >> 64, b_lo = (u64)b;
    u128 p01 = (u128)(a_lo) * b_lo;
    u128 p12 = (u128)(a_hi) * b_lo + (u64)(p01 >> 64);
    u64 t_hi = p12 >> 64, t_lo = p12;
    p12 = (u128)a_lo * b_hi + t_lo;
    u128 p23 = (u128)(a_hi) * b_hi + (u64)(p12 >> 64) + t_hi;
    return make_u256((u64)p01 | (p12 << 64), p23);
}

u256 add256(u256 a, u256 b)
{
    u256 ret;
    ret.hi = a.hi + b.hi;
    ret.lo = a.lo + b.lo;
    if (ret.lo < a.lo || ret.lo < b.lo) ++ret.hi;
    return ret;
}

u256 sub256(u256 a, u256 b)
{
    u256 ret;
    ret.hi = a.hi - b.hi;
    ret.lo = a.lo - b.lo;
    if (ret.lo > a.lo)
        --ret.hi;
    return ret;
}

int cmp256(u256 a, u256 b)
{
    if (a.hi == b.hi && a.lo == b.lo)
        return 0;
    else if ((a.hi > b.hi) || ((a.hi == b.hi) && (a.lo > b.lo)))
        return 1;
    else
        return -1;
}

u256 shl256(u256 a)
{
    u256 ret;
    a.hi <<= 1;
    a.hi |= ((a.lo & MSB128) ? 1 : 0);
    a.lo <<= 1;
    ret.hi = a.hi;
    ret.lo = a.lo;
    return ret;
}

u512 shl512(u512 a)
{
    u512 ret;
    a.hi = shl256(a.hi);
    a.hi.lo |= ((a.lo.hi & MSB128) ? 1 : 0);
    a.lo = shl256(a.lo);
    ret.hi = a.hi;
    ret.lo = a.lo;
    return ret;
}

u256 mod256(u256 a, u256 b)
{
    u512 p;

    p.hi = make_u256(0, 0), p.lo = a;
    for (unsigned i = 0; i < 256; ++i)
    {
        p = shl512(p);
        if (cmp256(p.hi, b) >= 0)
        {
            p.hi = sub256(p.hi, b);
            p.lo.lo |= 1;
        }
    }
    return p.hi;
}

u128 pow_u128(u128 a, u128 t, u128 mod)
{
    u128 r = 1;
    for (; t; t >>= 1, a = mod256(mul128(a, a), make_u256(mod, 0)).lo)
        if (t & 1)
            r = mod256(mul128(r, a), make_u256(mod, 0)).lo;
    return r;
}

u128 in_u128()
{
    u128 k = 0;
    char c = getchar_unlocked();
    while (c < '0' || c > '9')
        c = getchar_unlocked();
    while (c >= '0' && c <= '9')
    {
        k = (k << 1) + (k << 3) + (c ^ 48);
        c = getchar_unlocked();
    }
    return k;
}

void out_u128(u128 x)
{
    if (x > 9)
        out_u128(x / 10);
    putchar_unlocked(x % 10 + '0');
}

u128 n_mr128(u128 mod)
{
    return mod;
}
u128 ni_mr128(u128 mod)
{
    u128 ni = mod;
    for (int _ = 0; _ < 6; ++_)
        ni *= 2 - ni * mod;
    return ni;
}
u128 reduce(u256 z, u128 n, u128 ni)
{
    u128 y = z.hi - mul128(z.lo * ni, n).hi;
    return (y & MSB128) ? y + n : y;
}
u128 mul_mr128(u128 a, u128 b, u128 n, u128 ni)
{
    return reduce(mul128(a, b), n, ni);
}
u128 r_mr128(u128 mod)
{
    return (~mod + 1) % mod;
}
u128 r2_mr128(u128 mod, u128 ni)
{
    u128 r2 = (~mod+ 1) % mod;
    for (int _ = 0; _ < 4; ++_) if ((r2 <<= 1) >= mod) r2 -= mod;
    for (int _ = 0; _ < 5; ++_) r2 = mul_mr128(r2, r2, mod, ni);
}
u128 add_mr128(u128 a, u128 b, u128 n)
{
    return (a < n - b) ? a + b : sub256(add256(make_u256(a, 0), make_u256(b, 0)), make_u256(n, 0)).lo;
}
u128 sub_mr128(u128 a, u128 b, u128 n)
{
    return (a < b) ? sub256(add256(make_u256(a, 0), make_u256(n, 0)), make_u256(b, 0)).lo : a - b;
}
u128 pow_mr128(u128 a, u128 k, u128 n, u128 ni, u128 r)
{
    u128 ret = r;
    while (k > 0)
    {
        if (k & 1) ret = mul_mr128(ret, a, n, ni);
        a = mul_mr128(a, a, n, ni);
        k >>= 1;
    }
    return ret;
}

u128 to_mr128(u128 a, u128 n, u128 ni, u128 r2)
{
    return reduce(mul128(n, r2), n, ni);
}
u128 from_mr128(u128 a, u128 n, u128 ni)
{
    return reduce(make_u256(a, 0), n, ni);
}

int is_prime(u128 n)
{
    static const u128 bases[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };
    if (n == 1 || ((!(n & 1)) && n > 2)) return 0;
    for (int i = 0; i < 12; ++i) if (n % bases[i] == 0) return n == bases[i];
    u128 d = n - 1;
    u128 x, y;
    u128 ni = ni_mr128(n);
    u128 r = r_mr128(n);
    u128 r2 = r2_mr128(n, ni);
    u128 rev = to_mr128(n - 1, n, ni, r2);
    int e = 0;
    while (~d & 1) d >>= 1, ++e;
    for (int i = 0; i < 12; ++i)
    {
        u128 p = to_mr128(bases[i], n, ni, r2);
        x = pow_mr128(p, d, n, ni, r);
        for (int t = 0; t < e && x > 1; ++t)
        {
            y = mul_mr128(x, x, n, ni);
            if (y == r && x != rev) return 0;
            x = y;
        }
        if (x != 1) return 0;
    }
    return 1;
}


int main(void)
{
    u128 q = in_u128();
    while (q--)
    {
        u128 x = in_u128();
        out_u128(x);
        putchar_unlocked(' ');
        if (is_prime(x))
            putchar_unlocked('1');
        else
            putchar_unlocked('0');
        putchar_unlocked('\n');
    }
    return 0;
}
0