Day 017-Q5 | Garner's Algorithm（中国剰余定理の一般化）

問題

$T$ 個のクエリが与えられる。各クエリでは $K$ 個の合同式 $x \equiv r_i \pmod{m_i}$ が与えられる。これらをすべて満たす最小の非負整数 $x$ を求めよ。解が存在しない場合は $-1$。$m_i$ は互いに素でない場合もある。

入力形式

T
K
r_1 m_1
...
r_K m_K

制約

$1 \le T \le 100$

$1 \le K \le 20$

$1 \le m_i \le 10^9$

$0 \le r_i < m_i$

入出力例

入力例 1

出力例 1

23
-1

ヒント (段階的開示)

ヒント1: 方向性

$m_i$ が互いに素なら通常の CRT。そうでない場合は2つずつマージする操作を繰り返す。

ヒント2: アプローチ

$x = m_1 t + r_1$ として $m_1 t \equiv r_2 - r_1 \pmod{m_2}$。$g = \gcd(m_1, m_2)$ として $g | (r_2 - r_1)$ なら解あり。$t_0 = \frac{r_2-r_1}{g} \cdot (m_1/g)^{-1} \pmod{m_2/g}$、$x \equiv r_1 + m_1 t_0 \pmod{\text{lcm}}$。

ヒント3: 誘導

def merge(r1, m1, r2, m2):
    g = gcd(m1, m2)
    if (r2 - r1) % g != 0:
        return None, None
    lcm = m1 // g * m2
    _, inv, _ = extended_gcd(m1 // g, m2 // g)
    t = ((r2 - r1) // g) * inv % (m2 // g)
    r = (r1 + m1 * t) % lcm
    return r, lcm

模範解答 (Python)

import sys
from math import gcd

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

def merge(r1, m1, r2, m2):
    g = gcd(m1, m2)
    if (r2 - r1) % g != 0:
        return None, None
    m2g = m2 // g
    lcm = m1 // g * m2
    _, inv, _ = extended_gcd(m1 // g, m2g)
    inv %= m2g
    diff = ((r2 - r1) // g) % m2g
    t = diff * inv % m2g
    r = r1 + m1 * t
    r %= lcm
    return r, lcm

def solve_crt(pairs):
    r, m = pairs[0]
    for r2, m2 in pairs[1:]:
        r, m = merge(r, m, r2, m2)
        if r is None:
            return -1
    return r

def solve():
    input_data = sys.stdin.read().split()
    idx = 0
    T = int(input_data[idx]); idx += 1
    for _ in range(T):
        K = int(input_data[idx]); idx += 1
        pairs = []
        for _ in range(K):
            r, m = int(input_data[idx]), int(input_data[idx+1])
            idx += 2
            pairs.append((r, m))
        print(solve_crt(pairs))

solve()

Step-by-Step 解説

12つの合同式のマージ
$x \equiv r_1 \pmod{m_1}$, $x \equiv r_2 \pmod{m_2}$ を1つにまとめる。$x = m_1 t + r_1$ を代入。

2解の存在条件
$\gcd(m_1, m_2) | (r_2 - r_1)$ のときのみ解あり（Bezout の定理）。

3拡張ユークリッドで逆元
$g$ で両辺を割ると $(m_1/g) t \equiv (r_2-r_1)/g \pmod{m_2/g}$。$m_1/g$ と $m_2/g$ は互いに素なので逆元が存在。

4新しい合同式
$x \equiv r_1 + m_1 t_0 \pmod{\text{lcm}(m_1, m_2)}$。

5K個に一般化
2個ずつ順番にマージしていく。各マージで法が lcm になる。

よくあるミス

ミス	原因	正しい書き方
`m1 * m2` でオーバーフロー	Pythonなら問題ないがC++では注意	`m1 // g * m2` の順で計算
`r` が負になる	`%` の結果が負	`r %= lcm` で正に
extended_gcd の係数を混同	ax + by = gcd の係数	`extended_gcd(m1//g, m2//g)` の x を使う

次のステップ

発展問題: Garner Algorithm を用いた多倍長整数の高速乗算（複数の mod で NTT）
応用: K個の mod で FFT → Garner で整数に復元

自己評価

完全理解おおむね理解要復習

Day 017-Q5 — Garner's Algorithm

問題