C++ 代码
#include<bits/stdc++.h>
using namespace std;
int exgcd(int a, int b, int& x, int& y)//不要忘记引用&
{
if (b == 0)
{
x = 1; y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
/*
裴蜀定理:
若d=(a,b),则存在整数x,y使得ax+by=d
且任意 ax+by 均为d的倍数
exgcd作用:求得ax+by=d时的x,y
思路:
首先递归至最底层(a%b==0),然后赋值x=1,y=0
进而不断通过下一层计算上一层的x,y值
*/
int main()
{
int n; cin >> n;
while (n--)
{
int x, y;
int a, b; scanf("%d%d", &a, &b);
exgcd(a, b, x, y);
printf("%d %d\n", x, y);
}
}