扩展欧几里得

从欧几里得讲起……

欧几里得的辗转相除法计算的是两个自然数a和b的最大公约数g，意思是能够同时整除a和b的自然数中最大的一个。
两个数的最大公约数通常写成GCD(a, b)，或者简写成(a, b)。
(Greatest Common Divisor)

计算方法……辗转相除!

作为数论中一个很基础的内容，它的形式很漂亮，代码也很干净。

$gcd(a,b) = gcd(b,a % b)$

证明过程

令 $r = a % b$ 则有 $a = k \times b + r$ 故可知 $r = a - k \times b$
现假设 $d$ 是 $a$ , $b$ 的一个公约数
则有 $d|a$ , $d|b$

又由上式可得 $d|(a - k \times b)$ 即 $d|r \iff d|(a%b)$
由此证明 $d$ 也是 $b$ 和 $(a%b)$ 的公约数
即 $gcd(a,b) = gcd(b,a\%b)$

注: $d|a$ 表示 $d$ 整除 $a$

代码实现

long long gcd(long long a,long long b)
{   return b == 0 ? a : gcd(b,a%b); }

贝祖等式……问题的开端!

贝祖等式(又称裴蜀等式)是一个形如 $ax + by = m$ 的方程。
而有整数解 $(x,y) \iff m = k \times gcd(a,b) , k \in \mathbb Z$ 。
裴蜀等式有解时必然有无穷多个解。

补充:特别的, $ax + by = 1 \iff gcd(a,b)=1$

而利用辗转相除法可以得到这一方程的整数特解。
而且不难发现，大多数情况下 $x$ 和 $y$ 总是一正一负。

一段巧妙的证明

从 $ax + by = gcd(a,b)$ 开始……
由于~~长得漂亮~~对称的结构,我们不妨设 $a \gt b$

当 $b = 0$ 时, $gcd(a,b) = a$ 这个时候我们的等式就变成了 $ax = a$ 的形态不难看出这时候的一组解 $(x,y) = (1,0)$
当 $b \not= 0$ 时候,我们可以得到
$ax_1 + by_1 = gcd(a,b)$
$bx_2 + (a\%b)y_2 = gcd(b,a\%b)$
又由于 $gcd(a,b) = gcd(b,a\%b)$
所以有 $ax_1 + by_1 = bx_2 + (a\%b)y_2$
定义可得 $a\%b = a - \lfloor {\cfrac{a}{b}} \rfloor \times b$ 将其带入上式
$ax_1 + by_1 = bx_2 + (a - \lfloor {\cfrac{a}{b}} \rfloor \times b)y_2$
$ax_1 + by_1 = bx_2 + ay_2 - (\lfloor {\cfrac{a}{b}} \rfloor \times b)y_2$
由 $a$ 和 $b$ 的对应系数相等,所以可推出
$x_1 = y_2$
$y_1 = x_2 - \lfloor {\cfrac{a}{b}} \rfloor y_2$

综上，我们推导出了求该等式特解的边界条件和递推过程。

代码实现

注意 gcd , x , y 变量均使用引用传参,这是为了每一步都能改变原始数据。

void exgcd(long long a, long long b, long long &gcd, long long &x, long long &y)
{
    if (b == 0)
    {
        gcd = a;
        x = 1;
        y = 0;
        return;
    }
    exgcd(b, a % b, gcd, x, y);
    long long xt = x, yt = y;
    x = yt;
    y = xt - a / b * yt;
    return;
}

应用举例

求解同余方程的最小正整数解 $ax \equiv 1 (\mod b)$ ,给出 $a$ 和 $b$ 。

分析

$ax \equiv 1 (\mod b) \iff ax + by = 1$
其中 $y$ 是我们引入的一个整数而且十有八九应该是负数。
但是有一个问题, $ax + by = 1$ 又不是 $ax + by = gcd(a,b)$
这是怎么牵扯上关系的呢?~~还不是你乱点鸳鸯谱~~

但是我们求出的 $x$ 十有八九是负数也有可能太大,怎么得到最小正整数解呢?
$ax + by = 1$
$ax + by + k \times ab - k \times ab= 1$
$a(x + kb) + b(y - ka)= 1$
故而我们使用 $(x' \% b + b)\%b$ 的方式计算最终结果

这里一开始我不太明白
后来想想,我们要求的是 $x'$ 在加上 $k$ 个 $b$ 之后最小的整数结果
前提: $x' \lt 0, b \gt 0$
由 $x'\%b$ 可以将其结果限制在 $[-b,0]$
当 $-b \lt x'\%b \lt 0$ 时候加 $b$ 便是最终结果了
当 $x'%b = 0$ 时候加 $b$ 再对 $b$ 取模便是0不会出现错误

这里涉及到负数的取模运算,但这个计算的结果是百家争鸣的,我们先以C++中的结果为准
在C++中,有 $-7 \% 3 = -1$
以 $a = 3, b = 10$ 为例解得 $x = -3,y = 1$
计算得到 $(-3 \% 10 + 10) \% 10 = 7$

代码实现

void exgcd(long long a, long long b, long long &gcd, long long &x, long long &y)
{
    if (b == 0)
    {
        gcd = a;
        x = 1;
        y = 0;
        return;
    }
    exgcd(b, a % b, gcd, x, y);
    long long xt = x, yt = y;
    x = yt;
    y = xt - a / b * yt;
    return;
}
int main()
{
    long long a,b;
    long long g,x,y;
    cin >> a >> b;
    exgcd(a,b,g,x,y);
    x = (x % b + b)%b;
    cout << x << endl;
    return 0;
}