結果

問題 No.1339 循環小数
ユーザー 👑 seekworser
提出日時 2024-01-07 17:46:10
言語 Nim
(2.2.0)
結果
AC  
実行時間 43 ms / 2,000 ms
コード長 6,262 bytes
コンパイル時間 4,561 ms
コンパイル使用メモリ 87,556 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-27 19:28:05
合計ジャッジ時間 6,160 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2])
{.checks: off.}
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")
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0