扩展欧几里得算法

原题链接：877. 扩展欧几里得算法 - AcWing题库

前导知识

贝祖定理：

设a,b是不全为0的整数

则存在整数x,y，使得ax + by = gcd(a,b)

可以得到：

设a,b是不全为0的整数，ax + by = 1的充要条件是，a和b互质

所以存在逆元需要a和p互质

解题思路

因为我们知道ax + by = gcd(a,b)，又知道欧几里得算法gcd(a,b) = gcd(b,a % b)

我们可以将这两者结合起来：

ax + py = gcd(a,p) = gcd(p,a%p)

px1 + (a%p)p1 = gcd(p,a%p)

px1 + (a - floor(a / p) * p)y1 = gcd(p,a%p)

ay1 + p(x1 - floor(a / p) * y1) = gcd(a,p) = gcd(p,a%p)

所以：x = y1，y = x1 - floor(a / p) * y1

在最后阶段算到欧几里得算法算到最后一层也就是b = 0时：ax + by = gcd(a,b) = ax + 0y = a 于是x = 1,y = 0

我们可以通过，一层一层的欧几里得算法递归来一次一次计算xi和yi，到最后一层再一层一层向上更新xi和yi

源代码

#include <iostream>
#include <cstdio>

using namespace std;

int func(int a,int b,int &x,int &y)//引用x和y才能更新上一层
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int x1,y1,gcd;
    gcd = func(b,a%b,x1,y1);
    x = y1;
    y = x1 - a / b * y1;
    return gcd;
}

int main()
{
    int n;
    cin >> n;
    for(int v = 0;v < n;v ++)
    {
        int a,b,x,y;
        scanf("%d%d",&a,&b);
        func(a,b,x,y);
        printf("%d %d\n",x,y);
    }
    return 0;
}