結果
| 問題 | No.1339 循環小数 |
| ユーザー |
👑  seekworser
|
| 提出日時 | 2024-01-07 17:35:29 |
| 言語 | Nim (2.0.2) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,246 bytes |
| コンパイル時間 | 4,893 ms |
| コンパイル使用メモリ | 87,664 KB |
| 実行使用メモリ | 13,480 KB |
| 最終ジャッジ日時 | 2024-01-07 17:35:39 |
| 合計ジャッジ時間 | 9,436 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
13,480 KB |
| testcase_01 | AC | 2 ms
6,676 KB |
| testcase_02 | AC | 2 ms
6,676 KB |
| testcase_03 | AC | 2 ms
6,676 KB |
| testcase_04 | AC | 2 ms
6,676 KB |
| testcase_05 | AC | 2 ms
6,676 KB |
| testcase_06 | AC | 2 ms
6,676 KB |
| testcase_07 | AC | 2 ms
6,676 KB |
| testcase_08 | AC | 2 ms
6,676 KB |
| testcase_09 | AC | 2 ms
6,676 KB |
| testcase_10 | AC | 2 ms
6,676 KB |
| testcase_11 | AC | 8 ms
6,676 KB |
| testcase_12 | AC | 9 ms
6,676 KB |
| testcase_13 | AC | 8 ms
6,676 KB |
| testcase_14 | AC | 8 ms
6,676 KB |
| testcase_15 | AC | 8 ms
6,676 KB |
| testcase_16 | AC | 7 ms
6,676 KB |
| testcase_17 | AC | 9 ms
6,676 KB |
| testcase_18 | AC | 7 ms
6,676 KB |
| testcase_19 | AC | 6 ms
6,676 KB |
| testcase_20 | AC | 7 ms
6,676 KB |
| testcase_21 | TLE | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
ソースコード
import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2])
import strutils
ImportExpand "cplib/math/euler_phi.nim" <=== "when not declared CPLIB_MATH_EULER_PHI:\n const CPLIB_MATH_EULER_PHI* = 1\n import sequtils\n proc euler_phi*(n: int): int =\n result = n\n var n = n\n for i in 2..<n:\n if i+i > n:\n break\n if n mod i == 0:\n result -= result div i\n while n mod i == 0:\n n = n div i\n if n > 1:\n result -= result div n\n\n proc euler_phi_list*(n: int): seq[int] =\n result = (0..n).toSeq\n for i in 2..n:\n if result[i] == i:\n for j in countup(i, n, i):\n result[j] = result[j] div i\n result[j] *= (i - 1)\n discard\n"
ImportExpand "cplib/math/divisor.nim" <=== "when not declared CPLIB_MATH_DIVISOR:\n const CPLIB_MATH_DIVISOR* = 1\n import sequtils\n import tables\n import algorithm\n #[ import cplib/math/primefactor ]#\n when not declared CPLIB_MATH_PRIMEFACTOR:\n const CPLIB_MATH_PRIMEFACTOR* = 1\n #[ import cplib/math/inner_math ]#\n when not declared CPLIB_MATH_INNER_MATH:\n const CPLIB_MATH_INNER_MATH* = 1\n proc mul*(a, b, m: int): int {.importcpp: \"(__int128)(#) * (#) % (#)\", nodecl.}\n discard\n #[ import cplib/math/isprime ]#\n when not declared CPLIB_MATH_ISPRIME:\n const CPLIB_MATH_ISPRIME* = 1\n #[ import cplib/math/powmod ]#\n when not declared CPLIB_MATH_POWMOD:\n const CPLIB_MATH_POWMOD* = 1\n #[ import cplib/math/inner_math ]#\n proc powmod*(a, n, m: int): int =\n var\n rev = 1\n a = a\n n = n\n while n > 0:\n if n mod 2 != 0: rev = mul(rev, a, m)\n if n > 1: a = mul(a, a, m)\n n = n shr 1\n return rev\n discard\n proc isprime*(N: int): bool =\n let bases = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]\n if N == 2:\n return true\n if N < 2 or (N and 1) == 0:\n return false\n let N1 = N-1\n var d = N1\n var s = 0\n while (d and 1) == 0:\n d = d shr 1\n s += 1\n for a in bases:\n var t: int\n if a mod N == 0:\n continue\n t = powmod(a, d, N)\n if t == 1 or t == N1:\n continue\n block test:\n for _ in 0..<(s-1):\n t = powmod(t, 2, N)\n if t == N1:\n break test\n return false\n return true\n discard\n import random\n import std/math\n import algorithm\n import tables\n \n randomize()\n proc find_factor(n: int): int =\n if not ((n and 1) != 0): return 2\n if isprime(n): return n\n const m = 128\n while true:\n var x, ys, q, r, g = 1\n var rnd, y = rand(0..n-3) + 2\n proc f(x: int): int = (mul(x, x, n) + rnd) mod n\n while g == 1:\n x = y\n for i in 0..<r: y = f(y)\n for k in countup(0, r-1, m):\n ys = y\n for _ in 0..<min(m, r-k):\n y = f(y)\n q = mul(q, abs(x-y), n)\n g = gcd(q, n)\n if g != 1: break\n r = r shl 1\n if g == n:\n g = 1\n while g == 1:\n ys = f(ys)\n g = gcd(n, abs(x - ys))\n if g < n:\n if isprime(g): return g\n elif isprime(n div g): return n div g\n return find_factor(g)\n \n proc primefactor*(n: int, sorted: bool = true): seq[int] =\n var n = n\n while n > 1 and not isprime(n):\n var p = find_factor(n)\n while n mod p == 0:\n result.add(p)\n n = n div p\n if n > 1: result.add(n)\n if sorted: return result.sorted\n \n proc primefactor_cnt*(n: int): Table[int, int] =\n for p in primefactor(n):\n if p in result: result[p] += 1\n else: result[p] = 1\n discard\n proc divisor_naive(x: int, sorted: bool): seq[int] =\n for i in 1..x:\n if i*i > x: break\n if x mod i == 0:\n result.add(i)\n if i*i != x:\n result.add(x div i)\n if sorted: result.sort\n\n proc divisor*(x: int, sorted: bool = true): seq[int] =\n if x <= 1000_000: return divisor_naive(x, sorted)\n var factor = primefactor(x).toCountTable.pairs.toSeq\n var ans = newSeq[int](0)\n proc dfs(d, x: int) =\n if d == factor.len:\n ans.add(x)\n return\n var mul = 1\n for i in 0..factor[d][1]:\n dfs(d+1, x*mul)\n if i != factor[d][1]: mul *= factor[d][0]\n dfs(0, 1)\n if sorted: ans.sort\n return ans\n discard\n"
ImportExpand "cplib/math/powmod.nim" <=== ""
var t = stdin.readLine.parseint
var ans = newSeq[int](0)
for _ in 0..<t:
var n = stdin.readLine.parseint
while n mod 2 == 0: n = n div 2
while n mod 5 == 0: n = n div 5
if n == 1:
ans.add(1)
continue
for p in divisor(euler_phi(n)):
if powmod(10, p, n) == 1:
ans.add(p)
break
echo ans.join("\n")