前言：
\(\operatorname {exgcd}\)，顾名思义，是 \(\gcd\) 的一种扩展。\(\gcd\) 是求最大公因数，所用到的是辗转相除法，基于 \(\gcd(a,b)=\gcd(b,a\mod b) (a>b)\) 的原理，在学习 \(\operatorname{exgcd}\) 前，请确保已掌握 \(\gcd\) ,并懂得一点数学归纳法。如果您已掌握这些前置知识，请开始学习。
例题：
先看这样一道题，给定整数 \(a,b\) ，求 \(x,y\) 使得 \(ax+by=1\)。
性质：
性质1：
这显然是一道数学题（废话），考虑将原式根据乘法分配律转换为 \(\gcd(a,b)\times (\frac{a}{\gcd(a,b)}x+\frac{b}{\gcd(a,b)}y)=1\)。而如果两个整数乘积为 \(1\)，则他们一定为 \(1\)，因此 \(\gcd(a,b)=1\) ,换句话说，\(a,b\) 互质。
综上所述，我们得出性质，若原方程有解，当且仅当 \(a,b\) 互质。
性质2：
这个性质就比较简单，它实际上是类似于递归边界的东西，并不需要怎么推导。考虑当 \(a=1,b=0\) ,原方程有一组解为 \(x=1,y=0\)。
推导：
先看原式：\(ax+by=1\)。
设 \(m = a\mod b\)，\(k=\frac{a}{b}\)，则 \(a=bk+m\)。（其实就是余数和商）。
设有一个和原式一样的方程 \(x'm+y'b=1\)；
根据 \(m\) 的定义，转换为 \(x'(a-kb)+y'b=1\)；
将式子打开，变为 \(x'a-x'kb+y'b=1\)；
合并同类项，变为 \(x'a-(y'-kx')b=1\)；
可以发现一个神奇的事情，转化后的方程与原方程本质是一样的！唯一变化的只有 \(x\) 与 \(y\) 的值。也就是说，若 \(x'（a \mod b）+y'b=1\) 有解，那么 \(ax+by=1\) 也一定有解。而且这个解就是 \(x=x'\), \(y=y'-kx'\)（将所推方程代入）。而根据 \(\gcd\) 的写法，两个互质的数到递归边界时一定是 \(a=1,b=0\)。因为 \(a=1,b=0\) 的情况是有解的，所以 \(\gcd(a,b)=1\) 也是有解的，这也进一步证明了上面的性质。
如果你到这里都听懂了，那么下面的问题就很简单了，只需将 \(x,y\) 代入下面推出来的式子即可。
结论：
通过以上推导，可以得出：
- 原方程有解当且仅当 \(gcd(a,b)==1\)。
- 原方程解为 \( \begin{cases} x=1，y=0 & a=1,b=0 \\ x=x'，y=y'-kx (x'a \mod b +y'b = 1, k = \frac{a}{b}) & otherwise \\ \end{cases} \)
实现：
\(\operatorname{exgcd}\) 模版见下（递归）：
点击查看代码
void exgcd(int a, int b, int &x, int &y)
{
if(a == 1 && b == 0)//边界
{
x = 1, y = 0;
return ;
}
exgcd(b, a % b, y, x);
//这里之所以要交换x和y的位置，是因为b与a%b交换了，根据公式要把x,y也换过去
y = a / b * x;//按照公式赋值，由于是引用，所以x的值已经更改了。
}
总结：
第一次学 \(\operatorname{exgcd}\) 时，刚开始看到结论十分蒙，等到搞清楚证明时觉得这个证明妙不可言。笔者认为，学习 \(\operatorname{exgcd}\) 应不仅只会背代码，更要明白证明的过程，最好自己手推一遍。因为证明不仅是解决之后的许多与 \(\operatorname{exgcd}\) 的题有关，更能扩展思维，对数论有很大帮助。文章来源：https://www.toymoban.com/news/detail-648958.html
鉴于笔者也是蒟蒻，文中给出的部分推导过程与表述可能不严谨，欢迎大佬在评论区指出。
同时如果您对文章内容有不理解的地方，欢迎随时提问。文章来源地址https://www.toymoban.com/news/detail-648958.html
到了这里，关于算法学习笔记-exgcd的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
