結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー Jashinchan
提出日時 2022-10-05 16:11:17
言語 C
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 2,306 bytes
コンパイル時間 636 ms
コンパイル使用メモリ 33,708 KB
実行使用メモリ 8,356 KB
最終ジャッジ日時 2024-12-31 20:35:23
合計ジャッジ時間 44,767 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 TLE * 3
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'in_u128':
main.c:11:16: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration]
   11 |     while (c = getchar_unlocked(), c < 48 || c > 57)
      |                ^~~~~~~~~~~~~~~~
main.c: In function 'out_u128':
main.c:24:5: warning: implicit declaration of function 'putchar_unlocked' [-Wimplicit-function-declaration]
   24 |     putchar_unlocked(x - x / 10 * 10 + 48);
      |     ^~~~~~~~~~~~~~~~

ソースコード

diff # 

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

typedef __uint128_t u128;

u128 in_u128(void)
{
    u128 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_u128(u128 x)
{
    if (x >= 10)
        out_u128(x / 10);
    putchar_unlocked(x - x / 10 * 10 + 48);
}
void NL(void)
{
    putchar_unlocked('\n');
}
void SP(void)
{
    putchar_unlocked(' ');
}

u128 mul_mod_128(u128 a, u128 b, u128 m)
{
    u128 al = a & 0xffffffffffffffffull, ah = a >> 64;
    u128 bl = b & 0xffffffffffffffffull, bh = b >> 64;
    u128 ret = ah * bh % m;
    for (int _ = 0; _ < 64; ++_)
        ret = (ret << 1) % m;
    ret = (ret + al * bh + bl * ah) % m;
    for (int _ = 0; _ < 64; ++_)
        ret = (ret << 1) % m;
    ret = (ret + al * bl) % m;
    return ret;
}

u128 square_mod_128(u128 a, u128 m)
{
    return mul_mod_128(a, a, m);
}

u128 pow_mod_128(u128 a, u128 k, u128 m)
{
    return k ? mul_mod_128(pow_mod_128(square_mod_128(a, m), k >> 1, m), (k & 1 ? a : 1), m) : 1;
}

bool miller_rabin_128(u128 a, int s, u128 d, u128 n)
{
    u128 x = pow_mod_128(a, d, n);
    if (x == 1)
        return true;
    for (int r = 0; r < s; ++r)
    {
        if (x == n - 1)
            return true;
        x = square_mod_128(x, n);
    }
    return false;
}

bool is_prime(u128 n)
{
    u128 tiny_primes[25] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
    if (n <= 100)
    {
        for (size_t i = 0; i < 25; ++i)
        {
            if (n == tiny_primes[i])
            {
                return true;
            }
        }
        return false;
    }
    if (!(n & 1))
    {
        return false;
    }
    u128 d = n - 1;
    int s = 0;
    while (!(d & 1))
    {
        d >>= 1;
        ++s;
    }
    for (size_t i = 0; i < 25; ++i)
    {
        if (!miller_rabin_128(tiny_primes[i], s, d, n))
        {
            return false;
        }
    }
    return true;
}

int main(void)
{
    int Q;
    scanf("%d", &Q);
    while (Q--)
    {
        u128 x = in_u128();
        out_u128(x), SP(), putchar_unlocked(is_prime(x) ? '1' : '0');
        NL();
    }
    return 0;
}
0