中国余剰定理 (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