拓展欧几里得

如有侵权，请联系作者删除

辗转相除法

在介绍拓展欧几里得算法之前，先看看欧几里得算法（又称辗转相除法）

//辗转相除法，求两个数的最大公因数
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a%b);
}

具体原理这里省略，详情请参考原作者的文章：算法学习笔记(8)：拓展欧几里得 - 知乎 (zhihu.com)

拓展欧几里得

拓展欧几里得是可以在辗转相除的途中求出不定方程\(ax+by=c\)的一组解

可以发现：倒数第二行的\(3+6*3=21\)，可以改写成\(3=6*(-3)+21\)，也就是说：3可以被表示为6和21的线性组合。

倒数第三行，\(6+21*1=27\)，说明6可以被表示为21和27的线性组合，那么3也可以被表示为21和27的线性组合。具体地：

\(3=6*(-3)+21=(27-21)*(-3)+21=27*(-3)+21*4\)

这样一路推导下来，可以得到3表示为75和48的线性组合。那么\(75x+48y=3\)就能找到解了。

由上文可以得到求解\(ax+by=gcd(a,b)\)的一种方法。但如果\(c\)是其他数呢？

实际上，\(c\)必须是 \(gcd(a,b)\)的倍数，因为我们由方程 \(ax+by=c\) 两边除以 \(gcd(a,b)\) 可得 \(\frac{a}{gcd(a,b)}x+\frac{b}{gcd(a,b)}y=\frac{c}{gcd(a,b)}\) ，方程左边当然是整数，那么方程右边也必须是整数。所以\(c\)是\(gcd(a,b)\)的倍数。

这其实上是一个数论定理：

裴蜀定理

设\(a、b\)为正整数，则关于\(x、y\)的方程\(ax+by=c\)有整数解当且仅当\(c\)是\(gcd(a,b)\)的倍数

可以发现，通过求\(bx_0+(a\ mod\ b)y_0=c\)的解，可以得出\(ax+by=c\)的解。

前者等价于\(bx_0+(a-\lfloor a/b \rfloor)y_0=c\)，也就是\(ay_0+b(x_0-\lfloor a/b \rfloor y_0)=c\)，可以对比两者的系数，可以让： \[ \left\{ \begin{aligned} x & = y_0 \\ y & = x_0-\lfloor a/b \rfloor y_0 \\ \end{aligned} \right. \] 当\(b==0\)时递归结束即可，简化版如下：

int exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x); //这里交换了x和y
    y -= (a / b) * x;
    return d;
}

（这里其实有个普通版的，但是我偷懒了，直接搬了简化版qwq，若谷想看原版的，或者进一步探究原理的可以看看原文章：算法学习笔记(8)：拓展欧几里得 - 知乎 (zhihu.com)）

这样我们求出来的\(ax+by=gcd(a,b)\)的一组特解，那么通解是什么？

设除了已经求出来的\(x,y\)之外还有一组解\(x_1=x+\delta\)和\(y_1\)，那么由\(ax_1-a\delta+by==gcd(a,b)\)，可以得到\(ax_1+b(y-\frac{a\delta}{b})=gcd(a,b)\)，可以得到：

\(y_1=y-\frac{a\delta}{b}\)。

注意：我们还需要保证\(\delta\)和\(\frac{a\delta}{b}\)都是整数，后者等于\(\frac{a'}{b'}\delta\)，其中： \[ \left\{ \begin{aligned} a' & = \frac{a}{gcd(a,b)} \\ b' & = \frac{b}{gcd(a,b)} \\ \end{aligned} \right. \] 由于\(a'、b'\)互质，\(\delta\)应当等于\(kb'\)（\(k\)是整数），即： \[ \left\{ \begin{aligned} x_k & = x+k*\frac{b}{gcd(a,b)} \\ y_k & = y-k*\frac{a}{gcd(a,b)} \\ \end{aligned} \right. \] 这就是该不定方程的解。一般题目求的符合某些条件的解。