#942156 (Nim) No.1339 循環小数

提出ソース

結果

問題	No.1339 循環小数
ユーザー	👑 seekworser
提出日時	2024-01-07 17:46:10
言語	Nim (2.0.2)
結果	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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,816 KB
testcase_01	AC	2 ms 6,812 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	3 ms 6,944 KB
testcase_12	AC	2 ms 6,940 KB
testcase_13	AC	3 ms 6,940 KB
testcase_14	AC	2 ms 6,944 KB
testcase_15	AC	2 ms 6,944 KB
testcase_16	AC	3 ms 6,944 KB
testcase_17	AC	3 ms 6,944 KB
testcase_18	AC	2 ms 6,944 KB
testcase_19	AC	2 ms 6,944 KB
testcase_20	AC	2 ms 6,940 KB
testcase_21	AC	14 ms 6,944 KB
testcase_22	AC	14 ms 6,940 KB
testcase_23	AC	15 ms 6,940 KB
testcase_24	AC	14 ms 6,944 KB
testcase_25	AC	16 ms 6,940 KB
testcase_26	AC	16 ms 6,944 KB
testcase_27	AC	15 ms 6,940 KB
testcase_28	AC	15 ms 6,944 KB
testcase_29	AC	13 ms 6,940 KB
testcase_30	AC	13 ms 6,940 KB
testcase_31	AC	42 ms 6,940 KB
testcase_32	AC	43 ms 6,940 KB
testcase_33	AC	15 ms 6,944 KB
testcase_34	AC	4 ms 6,940 KB
testcase_35	AC	37 ms 6,944 KB
testcase_36	AC	15 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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")

yukicoder

結果

テストケース

ソースコード