扩展欧几里得定理

裴蜀定理:对于任意x，y，若满足$k_1x+k_2y=d$有解,则d一定为$k_1,k_2$的最大公约数

证明:

∵d为$x,y$的最大公约数

∴x,y一定为d的倍数

∴$k_1x+k_2y$也一定为d的倍数,则一定存在$k_1,k_2$为方程的一组解

通过欧几里得算法递归来求$k_1,k_2$

核心为gcd(a,b)=gcd(b,a%b)

若满足$k_1x+k_2y=d$,则$k_1y+k_2(x\%y)=d$,

显然,当$x\%y=0$时,$k_1=1,k_2=N$

因为$x\%y=x- \left \lfloor \frac{x}{y} \right \rfloor*y$

代入得$k_1y+k_2(x-\left\lfloor\frac{x}{y}\right\rfloor*y)=d$,

化简得$k_2x+(k_1-\left\lfloor\frac{x}{y}\right\rfloor*k_2)y=d$

为了方便计算,我们可以在递归时交换$k_1,k_2$

则会得到$k_1x+(k_2-\left\lfloor\frac{x}{y}\right\rfloor*k_1)y=d$

结合代码理解

int exgcd(int x,int y,int &k1,int &k2)
{
    if(!y)
    {
        k1 = 1, k2 = 0;
        return x;//当x%y=0时,更新x,y返回最大公约数
    }
    int d = exgcd(y, x % y, k2, k1);//交换x,y方便计算
    k2 -= x / y * k1;
    return d;
}

递归结束时$k_1,k_2$即为答案