ACL の inv gcd の正体

inv gcd

AtCoder Library の中の internal_math.hpp というファイルを開くと， inv_gcd という名前の関数があります． 2 つの整数 $aa$ ， $bb$ を受け取って， 2 数の最大公約数 $g=gcd(a,b)g = \mathrm{gcd}(a, b)$ と， $xa≡gmod bxa \equiv g \mod b$ なる $xx$ （ただし $0≤x<bg0 \leq x < \frac bg$）を返します．

この記事では，この関数がどのように実装されているか考えます．

手計算

まず， $a=100a = 100$ ， $b=529b = 529$ とした場合を手計算してみます．一般的に知られているやり方は，

$$529÷100=5⋯29100÷29=3⋯1329÷13=2⋯313÷3=4⋯1 \begin{alignedat}{5} 529 &\div &100 = 5 &\cdots &29 \\ 100 &\div &29 = 3 &\cdots &13 \\ 29 &\div &13 = 2 &\cdots &3 \\ 13 &\div &3 = 4 &\cdots &1 \\ \end{alignedat}$$

を変形して

$$29=529−5×10013=100−3×293=29−2×131=13−4×3 \begin{alignedat}{3} 29 &= &529 &- 5 \times &100 \\ 13 &= &100 &- 3 \times &29 \\ 3 &= &29 &- 2 \times &13 \\ 1 &= &13 &- 4 \times &3 \\ \end{alignedat}$$

とした上で，

$$1=1×13+(−4)×3=1×13+(−4)×(29−2×13)=(−4)×29+(1−(−4)×2)×13=(−4)×29+9×13=(−4)×29+9×(100−3×29)=9×100+(−4−9×3)×29=9×100+(−31)×29=9×100+(−31)×(529−5×100)=(−31)×529+(9−(−31)×5)×100=(−31)×529+164×100 \begin{aligned} 1 &= 1 \times 13 &&+ (-4) \times 3 \\ &= 1 \times 13 &&+ (-4) \times (29 - 2 \times 13) \\ &= (-4) \times 29 &&+ (1 - (-4) \times 2) \times 13 \\ &= (-4) \times 29 &&+ 9 \times 13 \\ &= (-4) \times 29 &&+ 9 \times (100 - 3 \times 29) \\ &= 9 \times 100 &&+ (-4 - 9 \times 3) \times 29 \\ &= 9 \times 100 &&+ (-31) \times 29 \\ &= 9 \times 100 &&+ (-31) \times (529 - 5 \times 100) \\ &= (-31) \times 529 &&+ (9 - (-31) \times 5) \times 100 \\ &= (-31) \times 529 &&+ 164 \times 100 \end{aligned}$$

から $164×100≡1mod 529164 \times 100 \equiv 1 \mod 529$ を得るものでしょう．これは，

$$1=x1×13+x2×3=x2×29+x3×13=x3×100+x4×29=x4×529+x5×100 \begin{aligned} 1 &= x_1 \times 13 + x_2 \times 3 \\ &= x_2 \times 29 + x_3 \times 13 \\ &= x_3 \times 100 + x_4 \times 29 \\ &= x_4 \times 529 + x_5 \times 100 \end{aligned}$$

としたときに

$$x1=1x2=−4x3=x1−x2×2x4=x2−x3×3x5=x3−x4×5 \begin{aligned} x_1 &= 1 \\ x_2 &= -4 \\ x_3 &= x_1 - x_2 \times 2 \\ x_4 &= x_2 - x_3 \times 3 \\ x_5 &= x_3 - x_4 \times 5 \\ \end{aligned}$$

という計算で $x5x_5$ が求められるということを意味します．さらに $x0=0x_0 = 0$ とすると

$$x0=0x1=1x2=x0−x1×4x3=x1−x2×2x4=x2−x3×3x5=x3−x4×5 \begin{aligned} x_0 &= 0 \\ x_1 &= 1 \\ x_2 &= x_0 - x_1 \times 4 \\ x_3 &= x_1 - x_2 \times 2 \\ x_4 &= x_2 - x_3 \times 3 \\ x_5 &= x_3 - x_4 \times 5 \\ \end{aligned}$$

となります．

一般化

以上の議論を全て文字に置き換えると， $a0=ba_0 = b$ ， $a1=aa_1 = a$ として互除法を

$$a0÷a1=q0⋯a2a1÷a2=q1⋯a3a2÷a3=q2⋯a4⋮an−1÷an=qn−1⋯0 \begin{aligned} a_0 \div a_1 &= q_0 \cdots a_2 \\ a_1 \div a_2 &= q_1 \cdots a_3 \\ a_2 \div a_3 &= q_2 \cdots a_4 \\ &\vdots \\ a_{n - 1} \div a_n &= q_{n - 1} \cdots 0 \\ \end{aligned}$$

とした上で，

$$x0=0x1=1x2=x0−x1×qn−2x3=x1−x2×qn−3⋮xn=xn−2−xn−1×q0 \begin{aligned} x_0 &= 0 \\ x_1 &= 1 \\ x_2 &= x_0 - x_1 \times q_{n - 2} \\ x_3 &= x_1 - x_2 \times q_{n - 3} \\ &\vdots \\ x_n &= x_{n - 2} - x_{n - 1} \times q_0 \\ \end{aligned}$$

としたときの $xnx_n$ が求めたかったものでした．

しかし，互除法では $q0,q1,q2,…q_0, q_1, q_2, \ldots$ の順番に求まるのに対し， $x0,x1,x2,…x_0, x_1, x_2, \ldots$ を求めるときは $qn−2,qn−3,qn−4,…q_{n - 2}, q_{n - 3}, q_{n - 4}, \ldots$ の順番で使うので，このままだと各 $qiq_i$ の値を保存しておかなければなりません．これを避けるため，計算順序を変えることを考えます．

行列表記

$$xi=xi−2−xi−1×qn−i x_i = x_{i - 2} - x_{i - 1} \times q_{n - i}$$

は，行列を用いると

$$(xi−1xi)=(011−qn−i)(xi−2xi−1) \begin{pmatrix} x_{i - 1} \\ x_{i} \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & -q_{n - i} \end{pmatrix} \begin{pmatrix} x_{i - 2} \\ x_{i - 1} \end{pmatrix}$$

と書くことができます．よって， $xnx_n$ を求める段階は

$$(xn−1xn)=(011−q0)(xn−2xn−1)(xn−2xn−1)=(011−q1)(xn−3xn−2)⋮(x2x3)=(011−qn−3)(x1x2)(x1x2)=(011−qn−2)(x0x1)=(011−qn−2)(01) \begin{aligned} \begin{pmatrix} x_{n - 1} \\ x_n \end{pmatrix} &= \begin{pmatrix} 0 & 1 \\ 1 & -q_0 \end{pmatrix} \begin{pmatrix} x_{n - 2} \\ x_{n - 1} \end{pmatrix} \\ \begin{pmatrix} x_{n - 2} \\ x_{n - 1} \end{pmatrix} &= \begin{pmatrix} 0 & 1 \\ 1 & -q_1 \end{pmatrix} \begin{pmatrix} x_{n - 3} \\ x_{n - 2} \end{pmatrix} \\ \vdots \\ \begin{pmatrix} x_{2} \\ x_{3} \end{pmatrix} &= \begin{pmatrix} 0 & 1 \\ 1 & -q_{n - 3} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \\ \begin{pmatrix} x_{1} \\ x_{2} \end{pmatrix} &= \begin{pmatrix} 0 & 1 \\ 1 & -q_{n - 2} \end{pmatrix} \begin{pmatrix} x_0 \\ x_1 \end{pmatrix} \\ &= \begin{pmatrix} 0 & 1 \\ 1 & -q_{n - 2} \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix} \end{aligned}$$

と書き換えることができます．これを一本にすると

$$(xn−1xn)=(011−q0)(011−q1)⋯(011−qn−2)(01) \begin{pmatrix} x_{n - 1} \\ x_n \\ \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & -q_0 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & -q_1 \end{pmatrix} \cdots \begin{pmatrix} 0 & 1 \\ 1 & -q_{n - 2} \end{pmatrix} \begin{pmatrix} 0 \\ 1 \\ \end{pmatrix}$$

となり， $q0,q1,q2,…q_0, q_1, q_2, \ldots$ の順に使って計算することができるようになりました．

変形

行列を左から順に計算すると，

$$A0=(1001)A1=A0(011−q0)A2=A1(011−q1)⋮An−1=An−2(011−qn−2)(xn−1xn)=An−1(01) \begin{aligned} A_0 &= \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} \\ A_1 &= A_0 \begin{pmatrix} 0 & 1 \\ 1 & -q_0 \end{pmatrix} \\ A_2 &= A_1 \begin{pmatrix} 0 & 1 \\ 1 & -q_1 \end{pmatrix} \\ \vdots \\ A_{n - 1} &= A_{n - 2} \begin{pmatrix} 0 & 1 \\ 1 & -q_{n - 2} \end{pmatrix} \\ \begin{pmatrix} x_{n - 1} \\ x_n \end{pmatrix} &= A_{n - 1} \begin{pmatrix} 0 \\ 1 \end{pmatrix} \\ \end{aligned}$$

となります．

行列 $(xyzw)\begin{pmatrix} x & y \\ z & w \end{pmatrix}$ に行列 $(011−qi)\begin{pmatrix} 0 & 1 \\ 1 & -q_i \end{pmatrix}$ を右からかけると $(yx−qiywz−qiw)\begin{pmatrix}y & x - q_iy \\ w & z - q_iw\end{pmatrix}$ となり，上の行（ $xx$ $yy$ ）と下の行（ $zz$ $ww$ ）は独立しています．よって，下の行のみに着目することで次のように書き換えることができます．

$$(z0, w0)=(0, 1)(z1, w1)=(w0, z0−q0w0)(z2, w2)=(w1, z1−q1w1)⋮(zn−1, wn−1)=(wn−2, zn−2−qn−2wn−2)xn=wn−1 \begin{aligned} (z_0,\; w_0) &= (0,\; 1) \\ (z_1,\; w_1) &= (w_0,\; z_0 - q_0w_0) \\ (z_2,\; w_2) &= (w_1,\; z_1 - q_1w_1) \\ \vdots \\ (z_{n - 1},\; w_{n - 1}) &= (w_{n - 2},\; z_{n - 2} - q_{n - 2}w_{n - 2}) \\ x_n &= w_{n - 1} \end{aligned}$$

こうして，互除法を行いながら $(z, w)(z,\;w)$ を更新することで $xnx_n$ が得られました．

確認

最初の $a=100a = 100$ ， $b=529b = 529$ の場合について計算して確かめてみます．

1. $(z0, w0)=(0, 1)(z_0,\; w_0) = (0,\; 1)$
2. $529÷100529 \div 100$ の商は $55$ なので $(z1, w1)=(w0, z0−5w0)=(1, −5)(z_1,\; w_1) = (w_0,\; z_0 - 5w_0) = (1,\; -5)$
3. $100÷29100 \div 29$ の商は $33$ なので $(z2, w2)=(w1, z1−3w1)=(−5, 16)(z_2,\; w_2) = (w_1,\; z_1 - 3w_1) = (-5,\; 16)$
4. $29÷1329 \div 13$ の商は $22$ なので $(z3, w3)=(w2, z2−2w2)=(16, −37)(z_3,\; w_3) = (w_2,\; z_2 - 2w_2) = (16,\; -37)$
5. $13÷313 \div 3$ の商は $44$ なので $(z4, w4)=(w3, z3−4w3)=(−37, 164)(z_4,\; w_4) = (w_3,\; z_3 - 4w_3) = (-37,\; 164)$

ちゃんと，最後に $w4w_4$ の値が $164164$ になっています．