[编程笔记]-Extended_Euclidean_Algorithm拓展欧几里得算法

前置

在学习拓展欧几里得算法前，建议先阅读裴蜀定理和乘法逆元两个页面了解本算法的作用。
[编程笔记]-Bezout’s_Lemma裴蜀定理
（乘法逆元页面尚未创建，可以去快速幂看看概念）

另外，如果你不知道欧几里得算法（辗转相除法），建议去约数基础部分先学习一下。
[编程笔记]-Divisor_Basis约数基础

实现

首先，既然是拓展欧几里得算法，肯定要从欧几里得算法拓展。

这里直接给出（证明见欧几里得算法）：gcd(a, b)==gcd(b, a%b)

已知当b==0时，gcd(a,b)=a。

拓展欧几里得算法就是要找非零整数x, y，使得**ax+by=gcd(a, b)**嘛（证明裴蜀定理），那么b==0时，x=1，b本来应该是任意数，这里特殊设置为0。

好，那么接下来就开始模拟递归返回的过程了——

假设我们按照定义写代码，下一层递归中的x、y记作x'、y'，可以得到：

若当前函数是gcd(a, b)，那么它的下一层递归也就应该是gcd(b, a%b)。

那么根据欧几里得定理，gcd(b, a%b)==gcd(a, b)，这里把它们记作d。

又根据裴蜀定理，可得b*x'+(a%b)*y'==d

这里讲一下%的展开方法：a%b=a-⌊a/b⌋*b

然后把得到的式子展开并重新整理：
y'*a+(x'-y'*⌊a/b⌋)*b==d

这个表达式表示的是gcd(b, a%b)得到的式子，也就是这一层递归的下一层递归得到的式子。

而在这一层递归中，x*a+y*b==d，

因此x=y', y=x'-y'*⌊a/b⌋

刚递归回溯到这一层时x、y实际是x'、y'，那如果在传参数的时候互换一下，x、y实际就成了y'、x'，那么就可以得出x、y的更新代码：

exgcd(b, a%b, y, x);
//x不变
y=y-a/b*x//鉴于运算顺序从左往右，要求先向下取整再运算，如果先乘了的话会出现误差，当然加个括号也行。

然后啊，经过验证，裴蜀定理就成立了。

说实话这个根据需要证明的定理构造过程在运用需要证明的定理方式下通过结果证明了需要证明的定理的定理证明方式还是有点不好理解的，甚至新接触数论的蒟蒻们（包括我TAT）会感受到这有一点逻辑悖论的味道。

那么重点就在于程序的完成了。

程序

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-=a/b*x;
    return d;
}

通解

另外，x、y是不唯一的，求通解如下：

已知ax₀+by₀==d

那么ax₀+by₀-(a*b)/d+(a*b)/d==d（(a*b)/d定为整数，因为d是最大公约数。）

化得a(x₀-b/d)+b(y₀+a/d)==d

那么就可以得到通解:
x=x₀-b/d*k,(k∈Z)
y=y₀+a/d*k,(k∈Z)

求乘法逆元

其实就是求解线性同余方程的特殊情况（b=1），看线性同余方程就行了。
[编程笔记]-Linear_Congruence_Equation线性同余方程

完结撒花o(￣︶￣)o

跟着醉酒·y总走了三遍没走明白，然后才想起来y总喝醉了Σ(っ °Д °;)っ
然后就在评论区里搞懂哩，以为自己学的有问题，想了好久(ノへ￣、)