結果

問題 No.1339 循環小数
コンテスト
ユーザー chaemon
提出日時 2020-11-28 14:41:17
言語 Nim
(2.2.0)
結果
AC  
実行時間 350 ms / 2,000 ms
コード長 2,098 bytes
コンパイル時間 3,363 ms
コンパイル使用メモリ 75,708 KB
実行使用メモリ 7,808 KB
最終ジャッジ日時 2024-09-13 01:58:38
合計ジャッジ時間 7,820 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

{.hints:off checks:off warnings:off assertions:on optimization:speed.}
import algorithm, sequtils, tables, macros, math, sets, strutils, strformat, sugar
when defined(MYDEBUG):
  import header

import streams
proc scanf(formatstr: cstring){.header: "<stdio.h>", varargs.}
#proc getchar(): char {.header: "<stdio.h>", varargs.}
proc nextInt(): int = scanf("%lld",addr result)
proc nextFloat(): float = scanf("%lf",addr result)
proc nextString[F](f:F): string =
  var get = false
  result = ""
  while true:
#    let c = getchar()
    let c = f.readChar
    if c.int > ' '.int:
      get = true
      result.add(c)
    elif get: return
proc nextInt[F](f:F): int = parseInt(f.nextString)
proc nextFloat[F](f:F): float = parseFloat(f.nextString)
proc nextString():string = stdin.nextString()

#{{{ gcd and inverse
proc gcd(a,b:int):int=
  if b == 0: return a
  else: return gcd(b,a mod b)
proc lcm(a,b:int):int=
  return a div gcd(a, b) * b
# a x + b y = gcd(a, b)
proc extGcd(a,b:int, x,y:var int):int =
  var g = a
  x = 1
  y = 0
  if b != 0:
    g = extGcd(b, a mod b, y, x)
    y -= (a div b) * x
  return g;
proc invMod(a,m:int):int =
  var
    x,y:int
  if extGcd(a, m, x, y) == 1: return (x + m) mod m
  else: return 0 # unsolvable
#}}}



proc modLog(a, b, p:int):int =
  var
    g = 1
    i = p
    b = b
  while i > 0:
    g = (g * a) mod p
    i = i div 2
  g = gcd(g, p)

  var
    t = 1
    c = 0
  while t mod g > 0:
    if t == b: return c
    t = (t * a) mod p
    c += 1
  if b mod g > 0: return -1

  t = t div g
  b = b div g

  var
    n = p div g
    h = 0
    gs = 1

  while h * h < n:
    gs = (gs * a) mod n
    h += 1

  var
    bs = initTable[int,int]()
    s = 0
    e = b
  while s < h:
    e = (e * a) mod n
    s += 1
    bs[e] = s

  s = 0
  e = t
  while s < n:
    e = (e * gs) mod n
    s += h
    if e in bs:
      return c + s - bs[e]
  return -1


let T = nextInt()

for _ in 0..<T:
  var N = nextInt()
  while N mod 2 == 0: N = N div 2
  while N mod 5 == 0: N = N div 5
  if N == 1:
    echo 1
  else:
    let r = 10 mod N
    echo modLog(r, invMod(r, N), N) + 1
0