ユークリッド互除法

2数の最大公約数を求める。

• ユークリッドの互除法

2数 $x,y$ の最大公約数 $gcd(x,y)$ とともに、

$$ax + by = gcd(x,y)$$

となる $(a,b)$ の組の1つも見つける。

組の1つが見つかれば、後は $u=\frac{x}{gcd(x,y)},v=\frac{y}{gcd(x,y)}$ として

$$..., (a-2v,b+2u), (a-v,b+u), (a,b), (a+v,b-u), (a+2v,b-2u), ...$$

が過不足なく全て等式を満たす組となる。

互除法とは直接関係ないが、一緒に使うことがある制約条件について。

• $x,y,z$ から、$ax+by=z$ となる $a,b$ を求める
• ただし $a \ge 0,b \ge 0$
• $a$ をあり得る中で最小にする

$a,b$ が正という条件で全探索する時、$a$ を最小（最大でもいいが）にしておくとやりやすい。

まず、$c=gcd(x,y)$ として、$z$ が $c$ の倍数で無い場合、等式は不可能である。

次に、拡張ユークリッド互除法で $a'x+b'y=c$ となる $a',b'$ を求める。$w=\frac{z}{c}$ とすると、$a'xw+b'yw=cw=z$ となり、$(a,b)=(a'w, b'w)$ が答えの一つとなる。

その後、非負チェックと $a$ の最小化を行う。$a$ は $v=\frac{y}{c}$ 単位でしか増減できないので $a\%v$ が最小値となる。負の場合だが、pythonでは $a$ が負であっても $a\%v$ で正の最小値が求まる。