题目描述

给定 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

算法

欧几里得算法

由欧几里得算法知:gcd(a,b)=gcd(b,a%b).
由裴蜀定理知:一定存在x1和y1满足ax1+by1=gcd(a,b),且也一定存在bx2+a%by2=gcd(b,a%b).
因此由欧几里得算法和裴蜀定理知:
gcd(a,b)=gcd(b,a%b).
ax1+by1=gcd(a,b).
bx2+a%by2=gcd(b,a%b).
故:
ax1+by1=bx2+a%by2.
即:
ax1+by1=bx2+a-a/bby2.
即:
ax1+by1=b(x2-a/by2)+ay2.
因为左右两边相等,因此a和b的系数分别对应相等,因此x1和y1可以从x2和y2得来,
而x2和y2又可以向下递归,直到递归到欧几里得算法的边界,得到一组x2和y2的解,再因此向上回溯依次算出其对应的x1和y1,
即为满足ax1+by1=gcd(a,b)的一组解x1和y1.

参考文献

https://www.acwing.com/activity/content/code/content/1113777/

C++ 代码

#include<iostream>
using namespace std;
typedef long long ll;
ll n,a,b,x,y;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    ll d=exgcd(b,a%b,x,y);
    ll temp=y;
    y=x-a/b*y;
    x=temp;
    return d;
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    while(n--)
    {
        cin>>a>>b;
        ll x,y;
        exgcd(a,b,x,y);
        cout<<x<<" "<<y<<'\n';
    }
    return 0;
}