扩展欧几里得算法

题目描述

给定 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≤105
,
1≤ai,bi≤2×109

输入样例：

2
4 6
8 18

输出样例：

-1 1
-2 1

扩展欧几里得如何解

设ax1+by1=gcd(a,b), bx2+(a%b)y2=gcd(b,a%b);
由gcd(a,b)=gcd(b,a%b),可得:
ax1+by1=bx2+(a%b)y2;
即:ax1+by1=bx2+(a-(a/b)*b)y2
          =ay2+bx2-(a/b)*by2;
即:ax1+by1=ay2 + b(x2-(a/b)*y2)
根据恒等定理,对应项相等，得:x1=y2; y1=x2-(a/b)*y2;
这样我们就得到了:x1，y1的值基于x2，y2，所以我们可以通过递归求解。

代码

#include <iostream>
using namespace std;
int gcd(int a,int b,int &x,int &y){
    if(!b) {
        x = 1,y = 0;
        return a;
    }

    int d = gcd(b,a % b,y,x);
    y -= a / b * x;
    return d;
}
int main(){
    int n;
    cin >> n;
    while(n --){
        int a,b,x,y;
        cin >> a >> b;
        gcd(a,b,x,y);
        cout << x << ' ' << y << endl;
    }
    return 0;
}