求解 \(ax + by = d\) 的解x和y。有解的条件为 d | gcd(a, b)
算法原理
假设现在我们已经得知了 \(by + (a \% b)x = d\) 的解 y 和 x
将 \(by + (a \% b)x = d\) 等价变形可以得到 \(ax + (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)}\) 则是方程的通解，代入即可验证其正确性
代码实现
/**
* 求解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;
}