cplib/math/inv_gcd.nim

• View this file on GitHub
• Last update: 2026-03-18 01:19:58+09:00

Required by

• cplib/convolution/convolution.nim
• cplib/convolution/convolution.nim

Verified with

• verify/convolution/convolution/convolution_dynamic_barrett_test.nim
• verify/convolution/convolution/convolution_dynamic_barrett_test.nim
• verify/convolution/convolution/convolution_dynamic_montgomery_test.nim
• verify/convolution/convolution/convolution_dynamic_montgomery_test.nim
• verify/convolution/convolution/convolution_static_barrett_test.nim
• verify/convolution/convolution/convolution_static_barrett_test.nim
• verify/convolution/convolution/convolution_static_montgomery_test.nim
• verify/convolution/convolution/convolution_static_montgomery_test.nim

Code

when not declared CPLIB_MATH_INVGCD:
    const CPLIB_MATH_INVGCD* = 1
    # @param b `1 <= b`
    # @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
    import std/math
    proc inv_gcd*(a, b: int): (int, int) =
        var a = floorMod(a, b)
        if a == 0: return (b, 0)
        var
            s = b
            t = a
            m0 = 0
            m1 = 1

        while t != 0:
            var u = s div t
            s -= t * u
            m0 -= m1 * u

            var tmp = s
            s = t
            t = tmp
            tmp = m0
            m0 = m1
            m1 = tmp
        if m0 < 0: m0 += b div s
        return (s, m0)

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/onlinejudge_verify/languages/nim.py", line 86, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page