算法简介：时间与智慧

欧几里得算法，简称 $\gcd$ ，常用的是辗转相减或辗转相除，是一个远古时期就被前人证明出来的算法。还有就是拓展欧几里得算法简称 $\tt exgcd$ ，是一个基于欧几里得算法用于求解 $Ax+By=C$ 方程的算法。非常的玄学，接下来会讲讲关于这些算法的流程代码以及复杂度分析。

算法演示：影照浮世风流

欧几里得算法：旧语新知 · 记忆中的沙丘

欧几里得算法，就是中国的辗转相减或辗转相除，本质上是让两个数不断地大数减小数（或者是用小数模大数），最后求出最大公约数，那么为什么会是这样呢？看如下证明

设一个 $a, b, c$ 分别表示 $\gcd(a,b) = \gcd(b,c)$ 这样一个式子的一部分，令他们三满足关系 $a=b\times q_0+c$（ $a$ 除以 $b$ 的余数是 $c$ ）如果 $b,c$ 有一个公因子 $q_1$ ，则这两个数可以有如下表示方法：
$$
b=k_0\times q_1,c=k_1\times q_1
$$
将其带入式子 $a = b\times q_0 + c$ ，可得：
$$
\begin{align}
a&=b\times q_0 + c\
a &= (k_0\times q_1)\times q_0 + k_1 \times q_1 \
a &= (k_0\times q_0 + k_1 )\times q_1
\end{align}
$$
提取公因数以后发现，$q_1$ 也是 $a$ 的因子，这样就证明了用辗转相除的正确性，辗转相除本身就是 $\gcd(a,b)=\gcd(b,a%b)$ 的过程，而又定义了 $c$ 是 $a%b$ 的值，这样就证明了正确性。

那么代码本质上就是模拟即可：

1
2
3

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

复杂度也不难证明，每一次我的计算规格至少减少 $\cfrac 1 2$ 所以说这是一个 $O(\log n)$ 的算法。

拓展欧几里得算法：旧语新知 · 二重拓展

拓展欧几里得就是一种基于欧几里得算法可以求出 $Ax+By=C$ 这样的方程的特解和通解的算法。首先我们要知道的是 $Ax+By=1$ 的时候，A 和 B 必须互质，否则无解。考虑反证法：

设 $A,B$ 不互质，那么 $A,B$ 可以表示成 $a = q × gcd ⁡ ( a , b ) , b = p × gcd ⁡ ( a , b )$ ，带入上面的式子，得到：
$$
q × \gcd ⁡ ( a , b ) × x + p × \gcd ⁡ ( a , b ) × y = 1
$$
两边同时除以 $gcd ⁡ ( A , B )$ ，得到：
$$
q x + p y = \cfrac 1 {\gcd ⁡ ( A , B ) }
$$
显然，如果此时 $A,B$ 不互质，那么等式的右边已经变成了一个小数，那么，该方程一定不存在整数解。

故只有当整数 $A,B$ 互质时，该方程才有整数解

顺便得到的就是：$A,B$ 互质的充要条件是，满足方程 $A x + B y = 1$ 有整数解

那么如果把这个方程两边同时扩大 $G$ 倍，$G$ 就是 $A,B$ 的最大公约数，那么同时也可以得到：$Ax+By=\gcd(A,B)$ 时方程有解，也就是说 $C$ 得是 $\gcd(A,B)$ 的倍数。

有了这条性质，我们就可以开始求特解了：

$Ax_0+By_0=\gcd(A,B)$
按照我们知道的这个性质的思路我们往下一步：
$Bx_1+(A%B) y_1=\gcd(B,A%B)$
由于欧几里得算法说过 $\gcd(A,B)=\gcd(B,A%B)$
那么可得 $Ax_0+By_0=Bx_1+(A%B)y_1$
由于 $A%B$ 可以看作 $A-\lfloor \cfrac A B \rfloor \times B$ ，代入可得 $Ax_0+By_0=Bx_1+(A-\lfloor \cfrac A B\rfloor\times B)y_1$
然后就得出了 $x_0 = y_1 , y_0 = x_1 - \lfloor\cfrac AB\rfloor \times y_1$ 的结论
不停的算下去，欧几里得算法一定会把它减成 $Gx + 0y = G$ 的形式，这里就得到 $x = 1, y = 0$ 接着回溯上去就可以了

int Exgcd(int a, int b, int &x, int &y) { // 返回 gcd 的值，求通解用
    if(b == 0) {
        x = 1, y = 0;
        return a;
    }
    else {
        int gcd = Exgcd(b, a % b, x, y);
        int save = y;
        y = x - a / b * y;
        x = save;
        return gcd;
    }
}

由于我们这里设的时直接 $C = \gcd(A,B)$ 那么通解就直接扩大回去就可以了，设 $x_0,y_0$ 是求出来的特解，那么有：
$$
x = x_0 + \cfrac B {\gcd(A,B)} \times k \
y = y_0 - \cfrac A {\gcd(A,B)} \times k \
(k ∈ Z)
$$
至此，一切结束。