扩展欧几里得算法（裴蜀定理）

裴蜀定理

如果有一个方程（a > 0, b > 0） ax + by = gcd(a,b)，我们如何求 {x,y} 呢？

ax + by = gcd(a,b) 作为已知条件

我们可以任意去算 ax + by = t

那么 t 一定是 gcd(a,b) 的倍数。因为 a 肯定是 gcd(a,b)的倍数， b 也一定是 gcd(a,b) 的倍数，那么 a * x, b * y 之后的 t 也一定是 gcd(a,b) 的倍数。

这样的话就很明确了，a 和 b 能凑出的最小正整数就是 gcd(a,b)

扩展欧几里得算法

接着我们的问题，我们需要找到系数 {x,y} 凑出最小正整数也就是最大公约数

递归来求

首先 ax + by = d

先特判一下，如果 a == d 那么返回 {1,0} 即可

辗转相除加速（也就是欧几里得算法）: (a mod b) * x + b * y = t

也就是：(a - a / b * b) * x + b * y = t， 继续化：a * x + b * (y - a / b * x) = t

那么 a 的系数没变 ，b 的系数变成了 y - a / b * x 一直递归下去即可

模板题

给定 n 对正整数 ai,bi对于每对数，求出一组 xi,yi 使其满足 ai×xi+bi×yi=gcd(ai,bi)

输入格式

第一行包含整数 n。

接下来 n 行，每行包含两个整数 ai,bi。

输出格式

输出共 n 行，对于每组 ai,bi，求出一组满足条件的 xi,yi，每组结果占一行。

本题答案不唯一，输出任意满足条件的 xi,yi 均可。

数据范围

1≤n≤10^5
1≤ai,bi≤2×10^9

输入样例：

2
4 6
8 18

输出样例：

-1 1
-2 1

代码：

#include <iostream>

using namespace std;

int t;
int a,b;

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

void solve()
{
    cin >> a >> b;
    
    int x, y;
    int gcd = exgcd(a, b, x, y);
    
    cout << x << " " << y << endl;
}

int main()
{
    cin >> t;
    while(t --){
        solve();
    }
    
    return 0;
}

加油