結果

問題 No.1339 循環小数
ユーザー chaemonchaemon
提出日時 2020-11-28 14:41:17
言語 Nim
(2.0.2)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,812 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 2 ms
6,820 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 3 ms
6,940 KB
testcase_12 AC 4 ms
6,944 KB
testcase_13 AC 3 ms
6,940 KB
testcase_14 AC 3 ms
6,940 KB
testcase_15 AC 3 ms
6,944 KB
testcase_16 AC 3 ms
6,940 KB
testcase_17 AC 3 ms
6,940 KB
testcase_18 AC 3 ms
6,940 KB
testcase_19 AC 3 ms
6,944 KB
testcase_20 AC 3 ms
6,940 KB
testcase_21 AC 191 ms
7,680 KB
testcase_22 AC 213 ms
7,680 KB
testcase_23 AC 205 ms
7,552 KB
testcase_24 AC 189 ms
7,680 KB
testcase_25 AC 204 ms
6,940 KB
testcase_26 AC 205 ms
7,680 KB
testcase_27 AC 203 ms
7,552 KB
testcase_28 AC 210 ms
7,680 KB
testcase_29 AC 173 ms
7,680 KB
testcase_30 AC 192 ms
7,808 KB
testcase_31 AC 308 ms
6,940 KB
testcase_32 AC 317 ms
6,944 KB
testcase_33 AC 211 ms
7,680 KB
testcase_34 AC 124 ms
6,944 KB
testcase_35 AC 350 ms
6,940 KB
testcase_36 AC 200 ms
7,680 KB
権限があれば一括ダウンロードができます

ソースコード

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