扩展欧几里得算法

裴蜀定理

对于任意正整数 a,b，那么一定存在整数 x,y，使得 ax+by=(a,b)

扩展欧几里得

首先看欧几里得算法的步骤：

1
2
3
4
5
6

int gcd(int a,int b){
    if(!b){
        return a;
    }
    return gcd(b,a%b);
}

可以发现，当 b=0 时，方程为 $a\cdot x+0\cdot y=(a,0)=a$，不难发现 $(1,0)$，为方程的一组解

接下来考虑其他情况：

首先已经得到了 $a’=b，b’=a%b$ 的一组解 $(x,y)$，记 $a$,$b$ 的最大公因数为 $d$ ，观察方程:
$$
b\cdot x+(a\bmod b)\cdot y=d
$$
由于 $a \bmod b = a- \lfloor \frac a b \rfloor \cdot b$，
$$
b\cdot x+(a- \lfloor \frac a b \rfloor \cdot b)\cdot y=d\
a\cdot y+ b\cdot(x-\lfloor \frac a b \rfloor\cdot y)=d
$$
因此 $a,b$ 的解就是 $(y,x-\lfloor \frac a b \rfloor\cdot y)$

为了方便，将 $x,y$ 交换，则答案为 $(x,y-\lfloor \frac a b \rfloor\cdot x)$

1
2
3
4
5
6
7
8
9
10

int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    
    int d=exgcd(b,a%b,y,x);
    y=y-a/b*x;
    return d;
}