結果

問題 No.3030 ミラー・ラビン素数判定法のテスト
ユーザー JashinchanJashinchan
提出日時 2022-08-27 19:12:35
言語 C
(gcc 12.3.0)
結果
TLE  
実行時間 -
コード長 3,426 bytes
コンパイル時間 294 ms
コンパイル使用メモリ 34,348 KB
実行使用メモリ 6,656 KB
最終ジャッジ日時 2024-10-14 15:45:43
合計ジャッジ時間 33,083 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 3 ms
5,248 KB
testcase_04 AC 7,774 ms
5,248 KB
testcase_05 AC 7,638 ms
5,248 KB
testcase_06 AC 1,944 ms
5,248 KB
testcase_07 AC 1,882 ms
5,248 KB
testcase_08 AC 1,892 ms
5,248 KB
testcase_09 TLE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'in_u128':
main.c:143:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration]
  143 |     char c = getchar_unlocked();
      |              ^~~~~~~~~~~~~~~~
main.c: In function 'out_u128':
main.c:158:5: warning: implicit declaration of function 'putchar_unlocked' [-Wimplicit-function-declaration]
  158 |     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 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;
}

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 r = n - 1;
    u128 x, y;
    int e = 0;
    while (~r & 1) r >>= 1, ++e;
    for (int i = 0; i < 12; ++i)
    {
        u128 p = bases[i];
        x = pow_u128(p, r, n);
        for (int t = 0; t < e && x > 1; ++t)
        {
            y = mod256(mul128(x, x), make_u256(n, 0)).lo;
            if (y == 1 && x != n - 1) return 0;
            x = y;
        }
        if (x != 1) return 0;
    }
    return 1;
}

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');
}

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