結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー iwkjosec
提出日時 2026-08-11 05:54:03
言語 C#
(.NET 10.0.201)
コンパイル:
dotnet_c
実行:
/usr/bin/dotnet_wrap
結果
AC  
実行時間 393 ms / 9,973 ms
+ 271µs
コード長 2,345 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 11,211 ms
コンパイル使用メモリ 172,540 KB
実行使用メモリ 191,256 KB
最終ジャッジ日時 2026-08-11 05:54:18
合計ジャッジ時間 9,789 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (86 ミリ秒)。
/home/judge/data/code/Main.cs(78,13): warning CA2022: 'System.IO.Stream.Read(byte[], int, int)' による不正確な読み取りを避ける (https://learn.microsoft.com/dotnet/fundamentals/code-analysis/quality-rules/ca2022) [/home/judge/data/code/main.csproj]
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

diff #
raw source code 

using System;
using System.IO;
using System.Numerics;

class Program
{
    static void Main()
    {
        Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
        var n = FastIO.Long();
        for (int i = 0; i < n; i++)
        {
            var x = (ulong)FastIO.Long();
            Console.WriteLine($"{x} {(MillerRabin(x) ? '1' : '0')}");
        }
        Console.Out.Flush();
    }

    public static ulong[] b64 = new ulong[] { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 };

    public static bool MillerRabin(ulong n)
    {
        if (n == 2) return true;
        if ((n & 1) == 0 || n < 2) return false;

        var n1 = n - 1;
        var s = BitOperations.TrailingZeroCount(n1);
        var d = n1 >> s;

        foreach (var b in b64)
        {
            var a = b;
            if (a >= n)
            {
                a %= n;
                if (a == 0) continue;
            }
            var x = ModPow(a, d, n);
            if (x == 1) continue;
            for (int i = 0; x != n1; i++)
            {
                if (i == s - 1) return false;
                x = ModMul(x, x, n);
            }
        }
        return true;
    }
    
    static ulong ModPow(ulong x, ulong n, ulong mod)
    {
        var res = 1ul;
        while (n != 0)
        {
            if ((n & 1) == 1) res = ModMul(res, x, mod);
            x = ModMul(x, x, mod);
            n >>= 1;
        }
        return res;
    }

    static ulong ModMul(ulong l, ulong r, ulong mod)
    {
        return (ulong)((UInt128)l * r % mod);
    }
}

public static class FastIO
{
    static Stream str = Console.OpenStandardInput();
    const int size = 1024;
    static byte[] buffer = new byte[size];
    static int ptr = size;

    static byte Read()
    {
        if (ptr == size)
        {
            str.Read(buffer, 0, size);
            ptr = 0;
        }
        return buffer[ptr++];
    }

    public static long Long()
    {
        var c = Read();
        while (c < 0x21)
        {
            c = Read();
        }
        var n = false;
        if (c == '-')
        {
            n = true;
            c = Read();
        }
        var ret = 0L;
        while (c > 0x20)
        {
            ret = ret * 10 + c - '0';
            c = Read();
        }
        return n ? -ret : ret;
    }
}
0