問題
$N$ 個の合同式 $x \equiv r_i \pmod{m_i}$ が与えられる。法 $m_i$ は互いに素とは限らない。すべてを満たす最小の非負整数 $x$ を求めよ。解が存在しなければ -1 を出力。
制約
| パラメータ | 範囲 | 備考 |
|---|---|---|
| $N$ | $1 \le N \le 10^5$ | 合同式の個数 |
| $m_i$ | $1 \le m_i \le 10^9$ | 法（互いに素とは限らない） |
| $r_i$ | $0 \le r_i < m_i$ | 余り |
入出力例
入力例1
3
2 3
3 5
2 7出力例1
23$23 \equiv 2 \pmod 3,\ 23 \equiv 3 \pmod 5,\ 23 \equiv 2 \pmod 7$。最小の非負解。
概念図: 2 式の逐次統合
ヒント
ヒント1（方向性）
2 式 $(r_1,m_1),(r_2,m_2)$ を統合。$g=\gcd(m_1,m_2)$ とし $(r_2-r_1)$ が $g$ で割り切れなければ解なし。割り切れれば法 $\mathrm{lcm}$ の 1 式にまとまる。
ヒント2（アプローチ）
$x=r_1+m_1t$ と置き $\frac{m_1}{g}t \equiv \frac{r_2-r_1}{g} \pmod{m_2/g}$。$\frac{m_1}{g}$ は $\frac{m_2}{g}$ と互いに素なので逆元が取れる。
ヒント3（ほぼ答え）
def merge(r1,m1,r2,m2):
g = gcd(m1,m2)
if (r2-r1)%g: return None
lcm = m1//g*m2
t = ((r2-r1)//g) * pow(m1//g, -1, m2//g) % (m2//g)
return (r1 + m1*t) % lcm, lcm模範解答
import sys
from math import gcd
def solve():
data = sys.stdin.buffer.read().split()
N = int(data[0])
r, m = 0, 1 # 恒真な合同式から開始
ok = True
for i in range(N):
ri = int(data[1 + 2 * i]); mi = int(data[2 + 2 * i])
g = gcd(m, mi)
if (ri - r) % g != 0:
ok = False
break
lcm = m // g * mi
m2g = mi // g
t = ((ri - r) // g) * pow(m // g, -1, m2g) % m2g
r = (r + m * t) % lcm
m = lcm
print(r if ok else -1)
solve()計算量: 1 式あたり $\gcd$ と逆元で $O(\log m)$、全体 $O(N \log \max m_i)$。pow(a, -1, mod) は Python 3.8+ のモジュラ逆元。
Step-by-Step 解説
Step 1: 2 式の統合条件
解を持つ必要十分条件は $r_1 \equiv r_2 \pmod{\gcd(m_1,m_2)}$。
Step 2: パラメータ表現
$x=r_1+m_1t$ を代入し両辺を $g$ で割ると $\frac{m_1}{g}t \equiv \frac{r_2-r_1}{g} \pmod{m_2/g}$。
Step 3: 逆元で $t$ を決定
$\gcd(m_1/g, m_2/g)=1$ より pow(m1//g, -1, m2//g) が存在。$x=(r_1+m_1t)\bmod \mathrm{lcm}$。
Step 4: 逐次畳み込み
初期 $(r,m)=(0,1)$ から 1 式ずつ統合。途中で条件不成立なら -1。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 互いに素前提で単純積 | $\gcd\ne1$ で誤答 | lcm=m//g*mi、逆元の法は $m_2/g$ |
| 負の差での判定 | 言語により % の符号 | Python では (ri-r)%g で正しく判定可 |
| 逆元の法を $m_2$ にする | $m_1/g$ は $m_2$ と非互素の場合あり | 法は $m_2/g$ |
次のステップ
- 発展問題: 巨大法（$\prod m_i$ が 64bit 超）を任意 mod で復元する Garner の一般形
- 発展問題: 複数素数 NTT の結果統合（Garner による多倍長回復）
自己評価
理解度: / /
自分の回答:
気づき・メモ: