結果
問題 | No.3030 ミラー・ラビン素数判定法のテスト |
ユーザー | iwkjosec |
提出日時 | 2022-10-20 18:05:36 |
言語 | C# (.NET 8.0.203) |
結果 |
AC
|
実行時間 | 507 ms / 9,973 ms |
コード長 | 3,595 bytes |
コンパイル時間 | 7,911 ms |
コンパイル使用メモリ | 167,364 KB |
実行使用メモリ | 180,916 KB |
最終ジャッジ日時 | 2024-06-30 10:05:32 |
合計ジャッジ時間 | 10,325 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 40 ms
22,912 KB |
testcase_01 | AC | 41 ms
22,656 KB |
testcase_02 | AC | 40 ms
23,036 KB |
testcase_03 | AC | 42 ms
22,896 KB |
testcase_04 | AC | 303 ms
25,984 KB |
testcase_05 | AC | 295 ms
25,968 KB |
testcase_06 | AC | 143 ms
26,112 KB |
testcase_07 | AC | 144 ms
25,984 KB |
testcase_08 | AC | 147 ms
28,312 KB |
testcase_09 | AC | 507 ms
180,916 KB |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (101 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System; using static System.Console; class Program { static void Main() { SetOut(new System.IO.StreamWriter(OpenStandardOutput()) { AutoFlush = false }); var n = FastIO.Long(); for (int i = 0; i < n; i++) { var x = (ulong)FastIO.Long(); WriteLine(x.ToString() + " " + (MillerRabin(x) ? "1" : "0")); } 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 = System.Numerics.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) { unchecked { if (mod <= uint.MaxValue) return l % mod * (r % mod) % mod; var high = Math.BigMul(l, r, out var low) % mod; if (high == 0ul) return low % mod; var lzc = 0; if (0 <= (long)mod) { lzc = System.Numerics.BitOperations.LeadingZeroCount(mod); mod <<= lzc; high = (high << lzc) | (low >> (64 - lzc)); low <<= lzc; } var mh = mod >> 32; var ml = (ulong)(uint)mod; var q = high / mh; var p = q * ml; high -= q * mh; high = (high << 32) | (low >> 32); if (high < p) { high += mod; if (high >= mod && high < p) { high += mod; } } high -= p; q = high / mh; p = q * ml; high -= q * mh; high = (high << 32) | (uint)low; if (high < p) { high += mod; if (high >= mod && high < p) { high += mod; } } return (high - p) >> lzc; } } } public static class FastIO { static System.IO.Stream str = System.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; } }