Day 129-Q4 | 一般化中国剰余定理（Generalized CRT）

問題

$N$個の合同式 $x \equiv r_i \pmod{m_i}$（$i=1,\dots,N$、$m_i$は互いに素とは限らない）をすべて満たす最小の非負整数$x$を、$\mathrm{lcm}(m_1,\dots,m_N)$を法として求めよ。解が存在しなければ-1。

入力形式

N
r_1 m_1
...
r_N m_N

制約

$1 \le N \le 200000$

$1 \le m_i \le 10^9$

$0 \le r_i < m_i$

入出力例

入力例1

出力例1

x≡2(mod4)とx≡0(mod6)をマージしてx≡6(mod12)。さらにx≡1(mod5)も矛盾なくマージされ最終解x=6(mod60)。

概念図

ヒント（段階的開示）

ヒント1（方向性）

$m_1,m_2$が互いに素でない場合、単純な代入では2式目に合わせられないことがある。$\gcd(m_1,m_2)$が1より大きいとき、$r_2-r_1$がその$\gcd$で割り切れなければ解は存在しない。

ヒント2（アプローチ）

2つの合同式を1つずつ逐次マージしていく。拡張ユークリッドの互除法で$m\cdot p+m_i\cdot q=\gcd(m,m_i)$を満たす$p,q$を求めるのがマージの核心。

ヒント3（誘導）

g, p, q = ext_gcd(m, mi)
if (ri - r) % g != 0:
    # 解なし
lcm = m // g * mi
diff = (ri - r) // g
x = (r + m * p * diff) % lcm

これを全ての合同式について繰り返す。

模範解答 (Python)

import sys


def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = ext_gcd(b, a % b)
    return g, y1, x1 - (a // b) * y1


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1

    r = 0
    m = 1
    ok = True

    for _ in range(n):
        ri = int(data[idx]); idx += 1
        mi = int(data[idx]); idx += 1
        if not ok:
            continue
        g, p, _q = ext_gcd(m, mi)
        if (ri - r) % g != 0:
            ok = False
            continue
        lcm = m // g * mi
        diff = (ri - r) // g
        x = (r + m * p * diff) % lcm
        r = x % lcm
        m = lcm

    print(-1 if not ok else r % m)


solve()

Step-by-Step 解説

1マージの意味
(r,m)は「これまでマージした合同式全体をまとめたx≡r(mod m)」を表す。1つずつマージしN個を1個に縮約する。

2解の存在条件
$(r_i-r)\bmod\gcd(m,m_i)=0$が必要十分条件。互いに素なら常に成り立つが、そうでなければ非自明な制約になる。

3拡張ユークリッドで解を構成
$mp+m_iq=g$を満たすpを使い$x=r+mp\cdot\frac{r_i-r}{g}$が両方の合同式を満たすことが確認できる。

4正規化
求めたxを新しい法lcm(m,m_i)で正規化し次のマージに使う。

5計算量
拡張ユークリッドはO(log max(m,m_i))、N-1回で全体O(N log max m_i)。

よくあるミス

ミス	原因	正しい書き方
互いに素だと決めつけ通常のCRT公式を使う	問題文の前提を読み落とす	必ず一般化版(gcd判定+拡張ユークリッド)を使う
解なし判定後もマージ計算を続けて例外を起こす	フラグ管理漏れ	`if not ok: continue`で早期スキップ
ext_gcdの返すpの役割を取り違える	拡張ユークリッドの意味の誤解	$mp+m_iq=g$のp(m側の係数)を使う
負の余りの正規化を余計にif分岐で書く	言語依存の%の挙動の思い込み	Pythonの%は常に非負を返すため追加分岐は不要

次のステップ

発展: 法が巨大(10^18級)でlcmがオーバーフローしうる言語では128bit相当の乗算が必要
次回予告: Convex Layers（凸包の層構造・Onion Peeling）

自己評価

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

Day 129-Q4 — 一般化中国剰余定理（Generalized CRT）

問題