数学基础

裴蜀定理和exgcd（扩展欧几里得）

首先，有个神奇的东西叫裴蜀等式/裴蜀定理。

这里有一个不定方程：\(ax+by=m\)。

裴蜀定理就是如果上面这个不定方程有解当且仅当\(gcd(a,b)|m\)。且当这个不定方程有解时，一定有无数多组解。

证明：（咕咕咕）

对于方程：\(ax+by=gcd(a,b)\)，我们可以用exgcd算法找到这个式子的一组解，然后就能就能推出\(ax+by=m\)的解。

而\(ax+by=gcd(a,b)\)可以通过递归构造解来解决：
\[ a \bmod b=a-\left \lfloor \frac{a}{b} \right \rfloor b \\假设存在x',y'使得x'b+y'(a \bmod b)=d \\则x'b+y'(a-\left \lfloor \frac{a}{b} \right \rfloor b)=d \\把上面这个式子化成ay'+b(x'-y'\left \lfloor \frac{a}{b} \right \rfloor) \\然后我们可以从这一层推出上一层的解x=y',y=(x'-y'\left \lfloor \frac{a}{b} \right \rfloor) \]
特别的，当g欧几里得算法递归到最低一层时，是这个样子的：\(gcd(c,d),d=0\)

那么对于这种情况我们就可直接得出当前这一层对应的不定方程\(cx''+dy''=gcd(c,d)=c\)的解：\(x''=1,y''=0\)然后就可以倒推出上一层的解。

当我们知道一组特解\(x0,y0\)之后，我们可以推出这个方程的通解：\(x=x0+\frac {b}{d}*k,y=y0-\frac {a}{d}*k\)其中\(d=gcd(a,b)\)。 至于这个式子是怎么来的，我们可以把式子变成\(ax+by+\frac{ab}{d}-\frac{ab}{d}=d\)然后提一下公因式就好了。另外，为什么ab要除d而不是其他数字是因为\(d=gcd(a,b)\)。

至此，我们只求出了\(ax+by=gcd(a,b)\)的通解。

我们只需要在两边乘上\(\frac {m}{gcd(a,b)}\)即可，因为这里不变的是系数（x0,y0均乘上这个式子，\(a\)和\(b\)不变），所以依旧可以用前面的方法求出特解。

如果遇到求出最小的正整数\(x\)，我们可以设$p=\frac{b}{d} $，而我们需要的最小正整数x就是:

\((x0\bmod p+p)\bmod p\)

代码(引自KSKUN——欧几里得算法和扩展欧几里得算法)：

int exgcd(int a, int b, int &x, int &y) {
    if(b == 0) {
        x = 1; // 设置b=0时的特殊解 
        y = 0;
        return a;
    }
    int ans = exgcd(b, a % b, x, y);
    int t = x; // 将x2, y2换算成x1, y1
    x = y;
    y = t - a / b * y;
    return ans;
}

线性同余方程

形如\(ax \equiv c\pmod b\)的式子我们称之为一元线性同余方程。

至于这个式子的求解，我们可以先把它化成\(ax+by=c\)的形式，其中\(y<0\)。就可以按照不定方程的做法做了。

数学基础

原文：https://www.cnblogs.com/GavinZheng/p/10988153.html