結果
問題 | No.1339 循環小数 |
ユーザー |
👑 |
提出日時 | 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 |
ソースコード
import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2]){.checks: off.}import strutilsImportExpand "cplib/math/euler_phi.nim" <=== "when not declared CPLIB_MATH_EULER_PHI:\n const CPLIB_MATH_EULER_PHI* = 1\n import sequtils\nproc 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\nif n mod i == 0:\n result -= result div i\n while n mod i == 0:\n n = n div i\nif 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\nresult[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 importtables\n import algorithm\n #[ import cplib/math/primefactor ]#\n when not declared CPLIB_MATH_PRIMEFACTOR:\n constCPLIB_MATH_PRIMEFACTOR* = 1\n #[ import cplib/math/inner_math ]#\n when not declared CPLIB_MATH_INNER_MATH:\n constCPLIB_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\na = 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\ndiscard\n proc isprime*(N: int): bool =\n let bases = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]\nif N == 2:\n return true\n if N < 2 or (N and 1) == 0:\n return false\n letN1 = N-1\n var d = N1\n var s = 0\n while (d and 1) == 0:\n d = d shr 1\ns += 1\n for a in bases:\n var t: int\n if a mod N == 0:\ncontinue\n t = powmod(a, d, N)\n if t == 1 or t == N1:\n continue\nblock 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\nimport 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 incountup(0, r-1, m):\n ys = y\n for _ in 0..<min(m, r-k):\n y = f(y)\nq = mul(q, abs(x-y), n)\n g = gcd(q, n)\n if g != 1: break\nr = r shl 1\n if g == n:\n g = 1\n while g == 1:\n ys = f(ys)\ng = gcd(n, abs(x - ys))\n if g < n:\n if isprime(g): return g\n elifisprime(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 nmod 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 pin result: result[p] += 1\n else: result[p] = 1\n discard\n proc divisor_naive(x: int, sorted: bool): seq[int] =\nfor 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:\nresult.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)\nproc dfs(d, x: int) =\n if d == factor.len:\n ans.add(x)\n return\n var mul = 1\nfor 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)\nif sorted: ans.sort\n return ans\n discard\n"ImportExpand "cplib/math/powmod.nim" <=== ""var t = stdin.readLine.parseintvar ans = newSeq[int](0)for _ in 0..<t:var n = stdin.readLine.parseintwhile n mod 2 == 0: n = n div 2while n mod 5 == 0: n = n div 5if n == 1:ans.add(1)continuefor p in divisor(euler_phi(n)):if powmod(10, p, n) == 1:ans.add(p)breakecho ans.join("\n")