中国余剰定理 (Chinese remainder theorem)

概要

未知の\(A\)について、

  • \(A \equiv X_i\) (mod \(Y_i\)) (\(i = 1, 2, ..., N\))

となる\(X_i\)が分かっている時に、

  • \(A \equiv X\) (mod \(\text{LCM}(Y_1, Y_2, ..., Y_N)\))

となる、一意の\(X\)を計算する。

具体的計算

\(A \equiv a\) (mod \(P\)) と \(A \equiv b\) (mod \(Q\)) から \(A \equiv c\) (mod LCM(\(P\), \(Q\))) の値を計算する。

\(g = \text{gcd}(P, Q)\) として、

\(P x + Q y = g\) となる \(x, y\) を拡張ユークリッドの互除法で求める。

そして、(\(\displaystyle \frac{Q y}{g} \equiv 1 (\text{mod } \frac{P}{g})\), \(\displaystyle \frac{P x}{g} \equiv 1 (\text{mod } \frac{Q}{g}\)) が成り立つことを利用して)

\(\displaystyle c = a \frac{Q y}{g} + b \frac{P x}{g}\) (mod LCM(\(P\), \(Q\))) とする。

計算量

\(\displaystyle O(N \log \max_i(Y_i))\)

実装

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

# V = [(X_i, Y_i), ...]: X_i (mod Y_i)
def remainder(V):
    x = 0; d = 1
    for X, Y in V:
        g, a, b = extgcd(d, Y)
        x, d = (Y*b*x + d*a*X) // g, d*(Y // g)
        x %= d
    return x, d

Verified

  • yukicoder: "No. 187 中華風 (Hard)": source (Python3, 865ms)

  • AtCoder: "DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選 - D問題: チップ・ストーリー 〜黄金編〜": source (Python3, 17ms)