exgcd 证明

· · 算法·理论

给定 a,b，求解 ax+by=\gcd(a,b) 的解。

考虑使用欧几里得算法的过程（这样 \gcd(a,b) 全程不会变），并把深层的解通过一些推导转化为浅层的解。

若 b=0，则解为 x=1,y=0。

否则，则递归求解方程 bx'+(a \bmod b)y' = \gcd(b,a \bmod b) 的解 x',y'。

注意到 \gcd(a,b) = \gcd(b,a\bmod b)，a \bmod b = a - \lfloor \frac{a}{b} \rfloor b。

可得出 bx'+(a - \lfloor \frac{a}{b} \rfloor b)y'=\gcd(a,b) 。

$ay' + b(x'-y'\lfloor \frac{a}{b} \rfloor) = \gcd(a,b)$ 。 至此，显然：$x=y',y=x'-y'\lfloor \frac{a}{b}\rfloor$。 ### 思路 构造一个流程，可以在 log 级别内结束。 递归算法，深层的 $a,b$ 可以用浅层的 $a,b$ 轻易表示出来，较为容易的推导解之间的转化关系。