题目描述

题目描述

给定n
对正整数$ai$,$bi$，对于每对数，求出一组$xi$,$yi$，使其满足$ai$$xi$+$biyi$=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

算法 扩展欧几里得算法

注意

用扩展欧几里得算出来的 系数x和y 是所有解当中|x|+|y|最小的

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
int exgcd(int a,int b,int &x,int &y) //传的x和y的地址，而不是值 
{                                    //本质还是辗转相除法，只是拓展了x和y的求值 
    if(!b){                  
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y=y-a/b*x;
    return d;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int a,b;
        scanf("%d%d",&a,&b);
        int x,y;
        exgcd(a,b,x,y);
        printf("%d %d\n",x,y);
    }
    return 0;
}