求解 $ax + by = d$ 的解x和y。有解的条件为 d | gcd(a, b)
算法原理
假设现在我们已经得知了 $by + (a % b)x = d$ 的解 y 和 x 将 $by + (a % b)x = d$ 等价变形可以得到 $ax + b(y - \lfloor \frac{a}{b} \rfloor x) = d$ 所以说如果我们先计算了$by + (a % b)x = d$ 的解 y 和 x，就可以得到我们最初想要计算的 $ax + by = d$ 中的x和y 设 $by + (a % b)x = d$ 的解 y 和 x分别为 y1 和 x1， 那么$ax + by = d$ 中的 x = x1， y = y1 - a / b * x1
易错点
扩展欧几里得的解并不唯一，假设 $ax + by = d$ 的一组解为 x1 和 y1，那么 $x1 + k * \frac{b}{gcd(a,b)}$ 和 $y1 - k * \frac{a}{gcd(a,b)}$ 则是方程的通解，代入即可验证其正确性 为了后续叙述的方便，我们用$t$代替$\frac{b}{gcd(a,b)}$。 $x1 + k * t$是解，那么$x1 - k * t$自然也是解，只需要y的解对应变化即可。那么当题目中要求我们求解x的最小正整数解时，接下来我们考虑应如何计算 分类讨论：
- 当$x_1$为正数时，如果$x_1<t$，此时的$x_1$就是最小正整数解，因为如果再减$t$答案就会变为负数了；如果$x_1>t$，操作应为
while (x > t) x -= t;，等价于x %= t - 当$x_1$为负数时，如果操作应为
while (x < 0) x += t;,等价于x = x % t + t,这里的操作是很巧妙的，第一次%t将$x$变化到绝对值小于$t$，这样再加t就能保证答案一定是正数且是最小的 综上所述，可以发现，负数比正数多了一个$+t$的操作，为了统一两者，$+t$之后只需要再%t一次即可。最终操作为x = (x % t + t) % t
代码实现
/**
* 求解ax + by = d
* 无解输出impossible
*/
#include <iostream>
using namespace std;
// 不管题目怎么变化，exgcd只负责求解 ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}
int gcd = exgcd(b, a % b, y, x);
y -= a / b * x;
return gcd;
}
int main()
{
int a, b, d, x, y;
cin >> a >> b >> d;
int t = exgcd(a, b, x, y);
// 有解的条件为m是gcd(a, b)的倍数
if (d % t) cout << "impossible" << endl;
else cout << d / t * x << ' ' << d / t * y << endl;
return 0;
}