本文整理梳理了一些有关扩欧算法的内容，力求深入浅出便于理解，对一些作者在初次接触此算法时的不解（比如一些不是很好看出来的“易得”“显然”hh）通过数学形式呈现与推导。本文涉及的数学推导非常简单。代码均采用C++。
限于作者能力有限可能有些地方表述不清，请读者多多包含！
【预备知识】
1.基础数论概念（整除、质数合数、gcd/lcm…或者说你已经懂了辗转相除法是怎么用）
2.递归、子函数
就让我们从原本的欧几里得算法开始。
【欧几里得算法】（EUCLID 即辗转相除法）
//a,b均为任意非负整数且不同时为零
int gcd(int a,int b)
{
if(b==0) return a;
else return gcd(b,a%b);
}
通过此可以求出a,b的最大公约数。
【扩展欧几里得算法】
就是欧几里得算法的推广，用于计算满足d=gcd(a,b)=ax+by的整系数x和y。
贝祖定理
若a,b是整数，设d=gcd(a,b)， 那么对于任意的整数x、y, d|ax+by, (p|q 表示p整除q)
特别地，一定存在整数x,y，使ax+by=d成立。
【应用1】求一元二次线性方程的整数解（ax+by=c）文章来源：https://www.toymoban.com/news/detail-581862.html
[ 思路 ]文章来源地址https://www.toymoban.com/news/detail-581862.html
到了这里，关于【数论】扩展欧几里得算法（EXTENDED-EUCLID）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
