欧几里得算法

辗转相除法，设 a≥ba\ge b 原理是：

gcd⁡(a,b)=gcd⁡(b,a−b)\gcd(a,b)=\gcd(b,a-b)

这个原因是 gcd⁡(a,b)∣a,gcd⁡(a,b)∣b\gcd(a,b)\mid a,\gcd(a,b)\mid b，所以相减同样满足 gcd⁡(a,b)∣(a−b)\gcd(a,b)\mid (a-b)。

我们知道取模实际上是减法，所以同理可得：

gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a,b)=\gcd(b,a\bmod b)

实现起来就是：

1
2
3
4
int gcd(int a, int b) {
    if (!b) return a;
    return gcd(b, a % b);
}

拓展欧几里得算法

裴蜀定理：对于任意正整数 a,ba,b 一定存在非零整数 x,yx,y 使 ax+by=gcd⁡(a,b)ax+by=\gcd(a,b)

如果已知：

by+(a mod b)x=dby+(a\bmod b)x=d\\

则能递推出：

by+(a−⌊ab⌋b)x=dax+b(y−⌊ab⌋x)=d\begin{aligned} by+(a-\lfloor\frac{a}{b}\rfloor b)x&=d\\ ax+b(y-\lfloor\frac{a}{b}\rfloor x)&=d\\ \end{aligned}

然后就写出 exgcd 算法求一组解了。

1
2
3
4
5
6
int exgcd(int a, int b, int& x, int& y) {
    if (b == 0) return x = 1, y = 0, a;
    int d = exgcd(b, a%b, y, x);
    y -= a/b * x;
    return d;
}

由于 ax0+by0=dax_0+by_0=d，那么满足条件的所有 x,yx,y 一定也满足：

a(x+bd)+b(y−ad)=da(x+\frac{b}{d})+b(y-\frac{a}{d})=d

也就有通解如下：

{x=x0+kbdy=y0−kadk∈Z\left \{ \begin{aligned} x&=x_0+k\frac{b}{d}\\ y&=y_0-k\frac{a}{d}\\ k&\in \Z \end{aligned}\right .

除以 dd 后这个数仍为整数。