拡張ユークリッドの互除法
(NumberTheory/Basic/extended_gcd.py)

• View this file on GitHub
• Last update: 2021-05-03 14:23:41+09:00

使い方

extended_gcd(a: int, b: int) -> Tuple[int, int, int]
$\gcd(a, b)$ の結果および $ax + by = \gcd(a, b)$ の整数解 $(x, y)$ を返す。計算量 $O(\log \min(a, b))$

mod_inv(a: int, m: int) -> int
整数 $m$ と互いに素な整数 $a$ について $ax \equiv 1 \pmod{m}$ を満たす $x$ を返す。計算量 $O(\log \min(a, m))$

Required by

• 中国剰余定理 (NumberTheory/ModularArithmetic/chinese_remainder_theorem.py)
• Garner のアルゴリズム (NumberTheory/ModularArithmetic/garner.py)
• 一次合同方程式 (NumberTheory/ModularArithmetic/linear_congruence.py)

Verified with

• TestCase/AOJ/NTL_1_E.test.py

Code

def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        g, y, x = extended_gcd(b, a % b)
        y -= (a // b) * x
        return g, x, y


def mod_inv(a, m):
    _, x, _ = extended_gcd(a, m)
    return x % m

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/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 "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page