从欧几里得讲起……

欧几里得的辗转相除法计算的是两个自然数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)$
这是怎么牵扯上关系的呢?还不是你乱点鸳鸯谱

由最大公约数的定义,总有$a|gcd(a,b)$而且$b|gcd(a,b)$
如果有$x,y \in \mathbb Z$则必定$(ax + by)|gcd(a,b)$
即若有$ax + by = m$则$m|gcd(a,b)$
当$m=1$时,就有$1|gcd(a,b)$
故而$gcd(a,b)$就只能等于$1$了

但是我们求出的$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;
}