裴蜀定理

• 内容：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立,并且gcd(a,b)是ax+by所能凑出来的最小正整数
• 推论：a,b互质的充分必要条件是存在整数x,y使ax+by=1.

扩展欧几里得算法推导过程

• 式子1：$ax+by=gcd(a,b)$
• 式子2：$bx^{\prime}+a\%by^{\prime}=gcd(b,a\%b)$
• 又因为$gcd(a,b)=gcd(b,a\%b)$,所以：$ax+by=bx^{\prime}+a\%by^{\prime}$
• 然后$a\%b=a-\lfloor\frac{a}{b}\rfloor\times b$,所以：$ax+by=bx^{\prime} +(a-\lfloor\frac{a}{b}\rfloor\times b) y^{\prime}$
• 根据待定系数法a和b的系数要相等
• 所以$x=y^{\prime},y=x^{\prime}-\lfloor\frac{a}{b}\rfloor y^{\prime}$
• 利用递归的性质,让下一层的$x^{\prime}和y^{\prime}$对上一层的$x和y$更新

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int n;
int exgcd(int a,int b,int &x,int &y)//x和y要传引用,方便直接改变x和y的值
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    int g=exgcd(b,a%b,x,y);//用下一层的值更新上一层的值
    int t=x;//先存一下下一层的x,因为x等会会被更新,要用下一层的x更新上一层的y
    x=y;//这两行的式子是通过ax+by=bx+a%by推导出来的
    y=t-a/b*y;
    return g;
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    while (n -- )
    {
        int a,b,x,y;
        cin>>a>>b;
        exgcd(a,b,x,y);    
        cout<<x<<" "<<y<<endl;
    }

}