给定整数 \(a, b, c\)。求一组整数解 \(x, y\) 使得：
\[ax + by = c \]或报告无解。
首先考虑 \(c = \gcd(a, b)\) 的简单情况，即：
\[ax + by = \gcd(a, b) \]当 \(c \mid \gcd(a, b)\) 时，我们可以将等式两边同时乘 \(\dfrac c{\gcd(a, b)}\) 已得到原问题的解，即 \(a \gets a \times \dfrac c{\gcd(a, b)},b \gets b \times \dfrac c{\gcd(a, b)}\)。根据裴蜀定理我们断言原问题有解当且仅当 \(c \mid \gcd(a, b)\)。
考虑这个求解弱化问题。
设：
\[ax_1 + by_1 = \gcd(a, b) \\ bx_2 + (a \bmod b)y_2 = \gcd(a, b) \]我们希望构造任意一组合法的 \(x_1,y_1\)。\(x_2,y_2\) 暂时辅助我们实现这一点。
那么：
\[\begin{aligned} \gcd(a, b) &= bx_2 + (a \bmod b)y_2 \\ &= bx_2 + \left( a - \left \lfloor \dfrac ab \right \rfloor \times b\right)y_2 \\ &= ay_2 + b\left(x_2- \left \lfloor \dfrac ab \right \rfloor y_2\right) \end{aligned} \]所以 \(\left\{ \begin{matrix}x_1 = y_2,\\ y_1=\left(x_2- \left \lfloor \dfrac ab \right \rfloor y_2\right) = \gcd(a, b) \end{matrix}\right.\) 就是一组合法的构造解。
所以问题转化成了求解 \(x_2,y_2\)。这与原问题相同。递归即可。
递归的边界是 \(b = 0\)。即需要构造一组解 \(x,y\) 使得：
\[ax + 0 \cdot y = a \]显然 \(\left\{ \begin{matrix}x=1,\\ y\in \mathbb Z\end{matrix}\right.\) 即可。这里取 \(y = 0\)。
int x, y;
void exgcd(int a, int b) {
if (!b) x = 1, y = 0;
else {
exgcd(b, a % b);
int _x_ = x, _y_ = y;
x = _y_;
y = _x_ - a / b * _y_;
}
}