結果

問題 No.8030 ミラー・ラビン素数判定法のテスト
ユーザー 真中満男
提出日時 2020-08-26 04:41:07
言語 Nim
(2.2.0)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 3 RE * 7
権限があれば一括ダウンロードができます
コンパイルメッセージ
/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]

ソースコード

diff # 

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 ""
0