Garner のアルゴリズム
(NumberTheory/ModularArithmetic/garner.py)

• View this file on GitHub
• Last update: 2021-05-03 15:04:52+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$ を求めるアルゴリズム。

使い方

pregarner(a: Sequence[int], m: Sequence[int], MOD: int) -> Tuple[int, Sequence[int], Sequence[int]]
互いに素でない $m_i, m_j (i \ne j)$ があるときに Garner のアルゴリズムを適応するための前処理 を行う。

• $1$ 番目の返り値が $-1$ のとき、$i = 0, 1, \cdots, n - 1$ について $x \equiv a_i \pmod{m_i}$ を満たす $x$ は存在しない。このときの $2, 3$ 番目の返り値は未定義。
• $1$ 番目の返り値が $-1$ でないとき、$1$ 番目の返り値は $\mathrm{MOD}$ 上の $\mathrm{lcm}(m[i])$ である。$2, 3$ 番目の返り値は前処理された $a$ と $m$ である。

pregarner(a: Sequence[int], m: Sequence[int], MOD: int) -> Tuple[int, Sequence[int], Sequence[int]]
$i = 0, 1, \cdots, n - 1$ について $x \equiv a_i \pmod{m_i}$ を満たす最小の非負整数 $x$ を $\mathrm{MOD}$ で割った余りを返す。そのような $x$ が存在しない場合は $-1$ を返す。計算量 $O(N^2)$

Depends on

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

Verified with

• TestCase/yukicoder/yuki0187.test.py

Code

from NumberTheory.Basic.extended_gcd import extended_gcd, mod_inv


def pregarner(a, m, MOD):
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    a, m = a[:], m[:]
    n = len(a)
    for i in range(n):
        for j in range(i):
            g = gcd(m[i], m[j])
            if (a[i] - a[j]) % g != 0:
                return -1, a, m
            m[i], m[j] = m[i] // g, m[j] // g
            gi = gcd(m[i], g)
            gj = g // gi
            while True:
                g = gcd(gi, gj)
                gi, gj = gi * g, gj // g
                if g == 1:
                    break
            m[i], m[j] = m[i] * gi, m[j] * gj
            a[i], a[j] = a[i] % m[i], a[j] % m[j]
    lcm = 1
    for i in range(n):
        lcm = lcm * m[i] % MOD
    return lcm, a, m


def garner(a, m, MOD):
    n = len(m)
    m = m + [MOD]
    coeff = [1] * (n + 1)
    res = [0] * (n + 1)
    for i in range(n):
        t = (a[i] - res[i]) * mod_inv(coeff[i], m[i]) % m[i]
        for j in range(i + 1, n + 1):
            res[j] = (res[j] + t * coeff[j]) % m[j]
            coeff[j] = coeff[j] * m[i] % m[j]
    return res[-1]

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