一.拓展欧几里得算法 $\quad O(n \ast log(a+b))$

1.1拓展欧几里得算法解决的问题:对于任意给定的两个正整数a,b,求解x,y使得ax+by=(a,b) //(a,b)的意思为,a和b的最大公约数

1.2问题的引入:裴蜀定理
给定任意一对正整数a,b,存在非零整数x,y,使得ax+by=(a,b)

1.3x与y的求解
$\color{brown}{由欧几里得算法拓展}$
设 d = gcd(a,b)
方式一:
$ exgcd(a,b,x,y)=exgcd(b,a\%b,y,x)\\\\ exgcd(b,a\%b,y,x) \Rightarrow \quad b \times y + (a-[\frac{a}{b}]\times b) \times x = d \Rightarrow \quad b\times(y-[\frac{a}{b}]\times x) + a \times x = d\\\\ ∴y更新为\color{red}{y-[\frac{a}{b}]\times x} $
方式二:
$ exgcd(a,b,x,y)=exgcd(b,a\%b,x,y)\\\\ exgcd(b,a\%b,x,y) \Rightarrow \quad b\times x + (a - [\frac{a}{b}]\times b)\times y=d \Rightarrow \quad p\times (x-[\frac{a}{b}]\times y)+a\times y\\\\ ∴y更新为\color{red}{x-[\frac{a}{b}]\times y},x更新为\color{red}{y} $

二.代码

方式一代码 $\quad O(n \ast log(a+b))$

#include<iostream>

using namespace std;

void exgcd(int a,int b,int& x,int& y)
{
    if(!b)
    {
        x=1,y=0;
        return ;
    }
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    while(n--)
    {
        int a,b,x,y;
        cin>>a>>b;
        exgcd(a,b,x,y);
        cout<<x<<' '<<y<<endl;
    }
    return 0;
}

方式二代码 $\quad O(n \ast log(a+b))$

#include<cstdio>
using namespace std;
void exgcd(int a,int b,int& x,int& y)
{
    if(!b)
    {
        x=1,y=0;
        return ;
    }
    exgcd(b,a%b,x,y);
    int t = y;
    y = x-a/b*y;
    x = t;
}
int main()
{

    int n;
    scanf("%d",&n);
    while(n--)
    {
        int a,b,x,y;
        scanf("%d%d",&a,&b);
        exgcd(a,b,x,y);
        printf("%d %d\n",x,y);
    }
    return 0;
}

$\color{brown}{喜欢题解的话,欢迎点赞、收藏、关注(三连)喔,如有什么疑问,欢迎评论下方指出}$