結果
問題 | No.3030 ミラー・ラビン素数判定法のテスト |
ユーザー | 真中満男 |
提出日時 | 2020-08-26 04:41:07 |
言語 | Nim (2.0.2) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,493 bytes |
コンパイル時間 | 4,443 ms |
コンパイル使用メモリ | 81,172 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-11-18 18:12:48 |
合計ジャッジ時間 | 4,506 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,820 KB |
testcase_02 | AC | 2 ms
6,816 KB |
testcase_03 | RE | - |
testcase_04 | RE | - |
testcase_05 | RE | - |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | RE | - |
testcase_09 | RE | - |
コンパイルメッセージ
/home/judge/data/code/Main.nim(1, 8) Warning: imported and not used: 'math' [UnusedImport] /home/judge/data/code/Main.nim(1, 14) Warning: imported and not used: 'sequtils' [UnusedImport]
ソースコード
import math, sequtils, random, strutils type ModInt = object v*: Natural m*: Positive proc toModInt*(v: int, m: Positive): ModInt = let v = if v < -m: ((v mod m) + m) mod m elif v < 0: v + m elif v < m: v else: v mod m result = ModInt(v: v, m: m) proc `+`*(a, b: ModInt): ModInt = var v = a.v + b.v if v >= a.m: v = v mod a.m result = ModInt(v: v, m: a.m) proc `*`*(a, b: ModInt): ModInt = var v = a.v * b.v if v >= a.m: v = v mod a.m result = ModInt(v: v, m: a.m) proc `^`*(a: ModInt, b: Natural): ModInt = if a.v == 0: return 0.toModInt a.m if b == 0: return 1.toModInt a.m if b == 1: return a if b > a.m: return a^(b mod (a.m-1)) let pow = a^(b div 2) if b mod 2 == 0: return pow * pow return pow * pow * a proc `+`*(a: int, b: ModInt): ModInt = a.toModInt(b.m) + b proc `+`*(a: ModInt, b: int): ModInt = a + b.toModInt(a.m) proc `-`*(a: ModInt, b: int): ModInt = a + -b proc `-`*(a, b: ModInt): ModInt = a + -b.v proc `-`*(a: int, b: ModInt): ModInt = a.toModInt(b.m) + -b.v proc `*`*(a: int, b: ModInt): ModInt = a.toModInt(b.m) * b proc `*`*(a: ModInt, b: int): ModInt = a * b.toModInt(a.m) proc `/`*(a: ModInt, b: int): ModInt = a * b.toModInt(a.m)^(a.m-2) proc `/`*(a, b: ModInt): ModInt = a / b.v proc `+=`*(a: var ModInt, b: ModInt) = a = a + b proc `+=`*(a: var ModInt, b: int) = a = a + b proc `-=`*(a: var ModInt, b: ModInt) = a = a - b proc `-=`*(a: var ModInt, b: int) = a = a - b proc `*=`*(a: var ModInt, b: ModInt) = a = a * b proc `*=`*(a: var ModInt, b: int) = a = a * b proc `/=`*(a: var ModInt, b: ModInt) = a = a / b proc `/=`*(a: var ModInt, b: int) = a = a / b proc modpow*(a, b: int, m: Natural): int = (a.toModInt(m)^b).v proc fromModInt*(a: ModInt) : Natural = result = a.v proc miller_rabin(n: Positive): bool = if n == 2: return true if n == 1 or (n and 1) == 0: return false var d = n-1 while (d and 1) == 0: d = d shr 1 for _ in 0..<25: var a = rand(n-2) + 1 t = d y = modpow(a, t, n) while t != n-1 and y != 1 and y != n-1: y = (y * y) mod n t = t shl 1 if y != n-1 and (t and 1) == 0: return false return true var N = stdin.readLine.parseInt for _ in 0 ..< N: var z = stdin.readLine.parseInt var k = if miller_rabin(z): 1 else: 0 stdout.write($z & " " & $k) echo ""