結果

問題 No.1339 循環小数
ユーザー chaemonchaemon
提出日時 2020-11-28 14:41:17
言語 Nim
(2.0.2)
結果
AC  
実行時間 328 ms / 2,000 ms
コード長 2,098 bytes
コンパイル時間 3,767 ms
コンパイル使用メモリ 67,088 KB
実行使用メモリ 11,572 KB
最終ジャッジ日時 2023-10-11 02:25:45
合計ジャッジ時間 8,786 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,368 KB
testcase_01 AC 2 ms
4,372 KB
testcase_02 AC 2 ms
4,372 KB
testcase_03 AC 2 ms
4,368 KB
testcase_04 AC 2 ms
4,368 KB
testcase_05 AC 2 ms
4,372 KB
testcase_06 AC 2 ms
4,372 KB
testcase_07 AC 2 ms
4,372 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 2 ms
4,372 KB
testcase_10 AC 2 ms
4,368 KB
testcase_11 AC 4 ms
4,936 KB
testcase_12 AC 5 ms
5,116 KB
testcase_13 AC 5 ms
4,964 KB
testcase_14 AC 5 ms
4,956 KB
testcase_15 AC 5 ms
5,060 KB
testcase_16 AC 4 ms
4,892 KB
testcase_17 AC 4 ms
4,852 KB
testcase_18 AC 5 ms
4,792 KB
testcase_19 AC 4 ms
4,640 KB
testcase_20 AC 4 ms
4,780 KB
testcase_21 AC 179 ms
11,344 KB
testcase_22 AC 197 ms
10,552 KB
testcase_23 AC 191 ms
10,064 KB
testcase_24 AC 179 ms
11,572 KB
testcase_25 AC 193 ms
9,764 KB
testcase_26 AC 192 ms
9,916 KB
testcase_27 AC 189 ms
11,056 KB
testcase_28 AC 198 ms
10,060 KB
testcase_29 AC 163 ms
10,908 KB
testcase_30 AC 179 ms
9,496 KB
testcase_31 AC 283 ms
8,280 KB
testcase_32 AC 287 ms
8,464 KB
testcase_33 AC 198 ms
10,032 KB
testcase_34 AC 118 ms
10,140 KB
testcase_35 AC 328 ms
8,340 KB
testcase_36 AC 186 ms
10,044 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