拡張ユークリッドの互除法

extgcd(a, b, &x, &y) {
    if (b == 0) {
	    x = 1;
	    y = 0;
	    return;
    }

	extgcd(b, a % b, y, x);

	y -= a / b * x;
	
	return
}

これは何をしているの〜

モチベーション

$ax + by = gcd(a, b)$ となる $x$ 、 $y$ を求めたい。

このような等式をベズーの等式という
$a$ と $b$ が互いに素である時、 $ax + by = 1$ であるが、この時の $x$ は $ax = 1\ (mod\ b)$ を満たす -> 逆元が求まるのでmodintでの除算ができる
整数問題でこの方程式を解く必要がある時がある

extgcd(a, b, x, y) -> $ax + by = gcd(a, b)$

について

$a = pb + q$

とすると

$(pb + q)x + by = gcd(a, b)$

$b(px + y) + qx = gcd(a, b)$

となる。この式は新たな変数 $s$ $t$ とでもおいて $bs + qt = gcd(a, b)$

ユークリッドの互除法で良く使うように

$gcd(a, b) = gcd(b,\ q)$

(で $q$ は $a$ を $b$ で割ったあまり)

$bs + qt = gcd(b, q)$

となり extgcd(b, a%b, y, x)を再帰的に解けば良いことになる。

aかbが0になった時に自明的に方程式が解けるので。ここから再帰を戻す。

ここで、 $s = (px + y) = (\lfloor\frac{a}{b}\rfloor x + y)$ という式から $y$ を復元する必要がある。

extgcd(b, a%b, y, x)はyに $s$ が代入されているため、

$y = s - \lfloor\frac{a}{b}\rfloor x$ という式変形があり、y -= a / b * xという処理が必要になっている。

$c = ax + by$ をみたす整数 $c$ は必ず $gcd(a, b)$ の倍数である。

$a$ も $b$ も $gcd(a, b)$ の倍数なので、 右辺 = $gcd(a, b)(a’x + b’y)$ と変形できる。-> どう考えても左辺が $gcd(a, b)$ の倍数でないといけない

ラメの定理

ユークリッドの互除法の計算回数の評価にまつわる定理

割って余りを取るという操作を、最悪でも小さいほうの数の十進法での桁数の約 5 倍繰り返せば、最大公約数に達する

毎回桁数の5倍程度に成るわけではなく、大抵はもっと早く終わる模様。