本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-05 12:56:35

给定 $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)$ 。

$bx'+ay'-\lfloor \frac{a}{b} \rfloor by' = \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$ 轻易表示出来，较为容易的推导解之间的转化关系。