借鉴大佬的思路

扩展欧几里得

定义：在得到整数a,b的最大公因子后，还希望得到整数$x,y$，使得$ax+by=gcd(a,b)$

我们记$ax_1+by_1=gcd(a,b)$为$1$

想一下辗转相除法的过程：

$gcd(a,b)=gcd(b,a \% b)$

然后根据定义我们又能得到另一个式子

$bx_2+(a \%b)y_2=gcd(b,a\%b)$为$2$

因为$gcd(a,b)=gcd(b,a \% b)$

所以我们又能得到$ax_1+by_1=bx_2+(a \%b)y_2$

$ax_1+by_1=bx_2+(a-b*\lfloor\frac ab\rfloor)y_2$

$ax_{1}+by_{1}=ay_{2}+b\left( x_{2}-\lfloor \dfrac{a}{b}\rfloor y_{2}\right)$

$x_1=y_2$,$y_1=x_2-\lfloor \dfrac{a}{b}\rfloor y_2$

$x_1,x_2$基于后面的$x_i,y_i$进行更新

当我们递归到底层的时候，就进行回溯，得到$x_1,y_1$

#include<bits/stdc++.h>

using namespace std;

int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y);
    int tmp=x;
    x=y;
    y =tmp- a / b * y;//这个时候x1=y2,y1=x2;
    return d;
}

int main()
{
    int n;
    scanf("%d", &n);

    while (n -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        int x, y;
        exgcd(a, b, x, y);
        printf("%d %d\n", x, y);
    }

    return 0;
}