中国剰余定理
(NumberTheory/ModularArithmetic/chinese_remainder_theorem.py)

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

概要

$m_0, m_1, \cdots, m_{n - 1}$ と $a_0, a_1, \cdots, a_{n - 1}$ について

\[\left\{\begin{array}{l}x \equiv a_0 \pmod{m_0}\\x \equiv a_1 \pmod{m_1}\\ \cdots \\x \equiv a_{n - 1} \pmod{m_{n - 1}}\end{array}\right.\]

を満たす $x$ を求めるアルゴリズム。

使い方

chinese_remainder_theorem(a: Sequence[int], m: Sequence[int]) -> Tuple[int, int]
$i = 0, 1, \cdots, n - 1$ について $x \equiv a_i \pmod{m_i}$ を満たす $x (0 \le x \lt \mathrm{lcm}(m[i]))$ とその周期 $\mathrm{lcm}(m[i])$ を返す。そのような $x$ が存在しない場合は $(-1, -1)$ を返す。計算量 $O(n \log \mathrm{lcm}(m[i]))$

Depends on

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

Verified with

• TestCase/yukicoder/yuki0186.test.py

Code

from NumberTheory.Basic.extended_gcd import extended_gcd


def chinese_remainder_theorem(a, m):
    r, M = 0, 1
    for i in range(len(a)):
        g, p, q = extended_gcd(M, m[i])
        if (a[i] - r) % g != 0:
            return -1, -1
        tmp = (a[i] - r) // g * p % (m[i] // g)
        r += M * tmp
        M *= m[i] // g
    return r % M, 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