結果
問題 | No.1339 循環小数 |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
{.hints:off checks:off warnings:off assertions:on optimization:speed.}import algorithm, sequtils, tables, macros, math, sets, strutils, strformat, sugarwhen defined(MYDEBUG):import headerimport streamsproc 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 = falseresult = ""while true:# let c = getchar()let c = f.readCharif c.int > ' '.int:get = trueresult.add(c)elif get: returnproc nextInt[F](f:F): int = parseInt(f.nextString)proc nextFloat[F](f:F): float = parseFloat(f.nextString)proc nextString():string = stdin.nextString()#{{{ gcd and inverseproc gcd(a,b:int):int=if b == 0: return aelse: 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 = ax = 1y = 0if b != 0:g = extGcd(b, a mod b, y, x)y -= (a div b) * xreturn g;proc invMod(a,m:int):int =varx,y:intif extGcd(a, m, x, y) == 1: return (x + m) mod melse: return 0 # unsolvable#}}}proc modLog(a, b, p:int):int =varg = 1i = pb = bwhile i > 0:g = (g * a) mod pi = i div 2g = gcd(g, p)vart = 1c = 0while t mod g > 0:if t == b: return ct = (t * a) mod pc += 1if b mod g > 0: return -1t = t div gb = b div gvarn = p div gh = 0gs = 1while h * h < n:gs = (gs * a) mod nh += 1varbs = initTable[int,int]()s = 0e = bwhile s < h:e = (e * a) mod ns += 1bs[e] = ss = 0e = twhile s < n:e = (e * gs) mod ns += hif e in bs:return c + s - bs[e]return -1let T = nextInt()for _ in 0..<T:var N = nextInt()while N mod 2 == 0: N = N div 2while N mod 5 == 0: N = N div 5if N == 1:echo 1else:let r = 10 mod Necho modLog(r, invMod(r, N), N) + 1