本文整理梳理了一些有關(guān)擴(kuò)歐算法的內(nèi)容，力求深入淺出便于理解，對一些作者在初次接觸此算法時的不解（比如一些不是很好看出來的“易得”“顯然”hh）通過數(shù)學(xué)形式呈現(xiàn)與推導(dǎo)。本文涉及的數(shù)學(xué)推導(dǎo)非常簡單。代碼均采用C++。
限于作者能力有限可能有些地方表述不清，請讀者多多包含！
【預(yù)備知識】
1.基礎(chǔ)數(shù)論概念（整除、質(zhì)數(shù)合數(shù)、gcd/lcm…或者說你已經(jīng)懂了輾轉(zhuǎn)相除法是怎么用）
2.遞歸、子函數(shù)
就讓我們從原本的歐幾里得算法開始。
【歐幾里得算法】（EUCLID 即輾轉(zhuǎn)相除法）
//a,b均為任意非負(fù)整數(shù)且不同時為零
int gcd(int a,int b)
{
if(b==0) return a;
else return gcd(b,a%b);
}
通過此可以求出a,b的最大公約數(shù)。
【擴(kuò)展歐幾里得算法】
就是歐幾里得算法的推廣，用于計算滿足d=gcd(a,b)=ax+by的整系數(shù)x和y。
貝祖定理
若a,b是整數(shù)，設(shè)d=gcd(a,b)， 那么對于任意的整數(shù)x、y, d|ax+by,? ?(p|q 表示p整除q)
特別地，一定存在整數(shù)x,y，使ax+by=d成立。
【應(yīng)用1】求一元二次線性方程的整數(shù)解（ax+by=c）文章來源：http://www.zghlxwxcb.cn/news/detail-581862.html
?[ 思路 ]文章來源地址http://www.zghlxwxcb.cn/news/detail-581862.html
到了這里，關(guān)于【數(shù)論】擴(kuò)展歐幾里得算法（EXTENDED-EUCLID）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
