扩展欧几里得算法

欧几里得算法，听起来很难的样子，但是如果换个名字 —— 辗转相除法。一切都变得正常多了。可以说这是用来算最小公倍数的最基本，最常用的算法了。
扩展欧几里得算法就比辗转相除法要看得更远。求最小公倍数是给定两个数 a,b，算出 gcd(a,b)。扩展的欧几里得算法是要求出两个数 x,y ，使得 ax+by=gcd(a,b)。

在这里要先引入一个定理 —— 裴蜀定理
若有一对正整数 a,b ，一定存在非零正数 x,y ，使得 ax+by=gcd(a,b)。
这个定理只是说明了这个问题是恒有解的，扩展欧几里得算法是直接构造这个解。

辗转相除法的成立归结于 gcd(a,b)\equiv gcd(b,a\mod b),那么可以用这个原理继续扩展。

a\mod b \equiv a-\lfloor \frac{a}{b} \rfloor * b
则有
ax+by=gcd(a,b)
by+(a\mod b)x=gcd(b,a\mod b)
gcd(a,b)\equiv gcd(b,a\mod b)
由此可得
by+(a-\lfloor \frac{a}{b}\rfloor* b)x=gcd(a,b)
将 a,b 的系数提取出来得
xa+(y-\lfloor \frac{a}{b} \rfloor* x)b=gcd(a,b)

例题：
给定 n 对正整数 a_i,b_i，对于每对数，求出一组 x_i,y_i，使其满足 a_i×x_i+b_i×y_i=gcd(a_i,b_i)。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n;

int exgcd(int a, int b,int &x, int &y)      //使用引用将x,y值传出
{
    if (!b)
    {
        x = 1, y = 0;                 //b为0，返回a,此时x=1,y=0
        return a;
    }
    int d = exgcd(b, a % b, y, x);       //此处需翻转，原因是b和a的位置进行了互换
    y -= a / b * x;                   //改变y的值

    return d;
}


int main()
{
    cin >> n;
    while (n--)
    {
        int a, b, x, y;
        cin >> a >> b;
        exgcd(a, b, x, y);

        cout << x << ' ' << y << endl;
    }

    return 0;
}