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

Modint を実装する過程で、拡張ユークリッドで得られる解の範囲について気になったことがあったことを思い出したので (かつ、あまり言及されているのを見たことがなかったので) メモを残しておきます。

$ax + by = 1$ の解

$a > b > 0, gcd(a, b)=1$ とします (そうでないときは gcd で割ったり符号を変えて解いた後戻せばいいです(gcd の方は割らずに進めてもいいです))

結論から言うと、 $-b < x < b, -a < y < a$ を満たす解が得られ、過程では overflow を気にする必要はないです。

$x \Leftarrow x + b, y \Leftarrow y - a$ などすると他の解は得られるので、ギリギリの解が求まっていますね。

雑な説明

$a = bq + r (0 \leq r < b)$ とすると、 $(bq + r)x + by = 1 \Leftrightarrow b(qx + y) + rx = 1$ より
$bX + rY = 1$ が成り立っているとき、 $x = Y, y = X - qY$ とすると解が得られます。

$-r < X < r, -b < Y < b$ だとすると、 $-b < x < b$ は言えます。

$y = X - qY = X - floor(a / b) * Y$ の方ですが、 $floor(a/b)=floor((a-r)/b)$ を使うと言えます。 $X, Y$ は符号が逆な感じになってます

ベースケースや境界をちゃんと言うのは許して

同様にして gcd が 1 でないときも $abs(x) < b / gcd(a, b) かつ abs(y) < a / gcd(a, b)$ が言えると思います。

宣伝

E - Balanced Piles

F - Paper Cutting

は今年の自信作なのでまだの人は解いて