一次合同方程式
(NumberTheory/ModularArithmetic/linear_congruence.py)

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

概要

一次合同方程式 $ax \equiv b \pmod{m}$ を解くアルゴリズム。

使い方

linear_congruence(a: int, b: int, m: int) -> Tuple[bool, int, int]
一次合同方程式 $ax \equiv b \pmod{m}$ に対して (解が存在するか, 最小の非負整数解, 解の周期) を返す。解が存在しない場合は (False, -1, -1) を返す。計算量 $O(\log \min(b, m))$

Depends on

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

Verified with

• TestCase/unittest/linear_congruence.unittest.test.py

Code

from NumberTheory.Basic.extended_gcd import extended_gcd


def linear_congruence(a, b, m):
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a

    if b % gcd(a, m) != 0:
        # 解なし
        return False, -1, -1
    g, x, y = extended_gcd(a, m)
    x *= b // g
    cycle = m // g
    x -= cycle * (x // cycle)
    return True, x, cycle

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