扩展欧几里得算法

裴蜀定理

法国数学家艾蒂安·裴蜀 Bézout 提出：指对于正整数 $a$ 和 $b$，它们的最大公约数 $d$ 是它们的线性组合 $ax+by$ 中的 最小正整数。也就是说，存在整数 $x$ 和 $y$，使得 $ax+by=d$，其中 $d$ 是 $a$ 和 $b$ 的最大公约数。

证明：首先我们知道，对于最大公约数 $d$，它一定满足 $d|(ax+by)$。也就是说 $ax+by\ge d$ 恒成立。因此该线性组合得到的最小正整数不会小于最大公约数 $d$，下面只要证明这个 $d$ 是可以取到的即可。

下面用 扩展欧几里得算法 进行构造性证明：

AC877. 扩展欧几里得算法

回忆欧几里得算法：

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

// addition
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    else {
        return gcd(b, a % b);
    }
}

核心代码：

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);

    y = y - (a / b) * x;

    return d;
}

边界情况下：此时一定是 ((a, b), 0)。剩下的情况考虑递归，注意用引用传递 x, y，当我们已经得到前面的系数之后，和欧几里得算法一样 a % b 照样可以使得方程成立，不过 x, y 会发生变化：

$$by+(a-\lfloor \frac{a}{b}\rfloor b)x=d\Rightarrow ax+b(y-\lfloor \frac{a}{b}\rfloor x)=d$$

因此只需要修改 y 即可。

注意答案是有无穷组的，假设我们找到了一组 $x,y$，那么有：

$$a(x_0-\frac{b}{d})+b(y_0+\frac{a}{d})=d$$

解集合：

$$\{\begin{array}{r}x=x_0-\frac{b}{d}\cdot k\\ y=y_0+\frac{a}{d}\cdot k\end{array}$$

TODO：是否所有的解都在这个解集合中呢？

线性同余方程

AC878. 线性同余方程

将这个问题转化为裴蜀等式：

$$ax\equiv b(\mathrm{mod}m)\Rightarrow \text{exist}y\in \mathbb{Z},ax=my+b\Rightarrow ax+m{y}^{\prime }=b$$

求系数 $x$，使得上述方程成立。首先判断等式成立的充分必要条件：$(a,m)|b$，一定是最大公约数的倍数才行，这是充要条件。

核心代码：

if (b % d != 0) {
    cout << "impossible" << endl;
}
else {
    cout << (long long)x * (b / d) % m << endl;
}

注意这里的 b 不一定是最大公约数的倍数，得判断：

• 如果不是，直接输出 impossible
• 如果是，那么需要根据方程 $ax+my=d$ 进行扩充，得到 $x=x_0\times b/d$
• 至于最后为什么要模 $m$，是因为将 $x$ 带入方程后 $a{x}_t\equiv ax\equiv b(\mathrm{mod}m)$，这样做可以避免 $x$ 过大