$\huge \color{orange}{成仙之路->}$ $\huge \color{purple}{算法基础课题解}$

扩展欧几里得算法

存在 $x,y$ 使得 $ax+by=\gcd(a,b)$

当 $b=0$ 时，$ax+by=a$，易得 $x=1,y=任何数$

当 $b\ne0$ 时，

因为 $$ax+by=\gcd(a,b)=\gcd(b,a \bmod b)$$

而 $$bx’+(a \bmod b)y’=\gcd(b,a \bmod b)$$

$$bx’+(a-\left\lfloor\dfrac{a}{b}\right\rfloor b)y’=\gcd(a,b)$$

$$ay’+b(x’-\left\lfloor\dfrac{a}{b}\right\rfloor y’)=ax+by$$

将 $x’$ 和 $y’$ 位置互换

$$ax’+b(y’-\left\lfloor\dfrac{a}{b}\right\rfloor x’)=ax+by$$

故

$$x=x’,y=y’-\left\lfloor\dfrac{a}{b}\right\rfloor x’$$

可参考： 欧几里得算法

完整代码

#include <bits/stdc++.h>

using namespace std;

int exgcd(int a, int b, int &x, int &y) {
    //b == 0
    if (!b) {
        x = 1, y = 0;
        return a;
    }

    //b != 0
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main() {
    int n;
    cin >> n;

    int a, b, x, y;
    while (n--) {
        cin >> a >> b;
        exgcd(a, b, x, y);
        cout << x << ' ' << y << endl;
    }

    return 0;
}