拓展歐幾里得模板
參考：哈爾濱理工大學(xué)ACM培訓(xùn)資料匯編/ACM-ICPC培訓(xùn)資料匯編*
基本原理 ：設(shè) a 和 b 不全為 0，則存在整數(shù) x,y 使得 xa yb=gcd(a,b)=c
對(duì)于輾轉(zhuǎn)相除法的最后一項(xiàng) 此時(shí) b=0,則 gcd(a,b)=1a 0b,（這個(gè)a,b是經(jīng)過(guò)gcd的最后一項(xiàng)a，b）

• 因?yàn)間cd(a,b)=gcd(b,a%b)
• 則有x *a y *b=x1 *b y1 * (a%b) 將等式右邊變形，
  b *x1 (a%b) *y1=b *x1 (a-(a/b) *b) *y1=a *y1 b *(x1-(a/b) *y1)
• 則，x=y1,y=x1-(a/b) *y1 則可由后向前迭代得到 x,y
• 解題思路 對(duì)于擴(kuò)展歐幾里德定理的題，一般都需要進(jìn)行一定的推導(dǎo)之后得到一個(gè)形式為 xa yb=c 的方程，然后根據(jù) c 確定解是否存在，如果 c 可以被 gcd(a,b)整除，那么方程有 解，否則方程無(wú)解。而且所得的解是不唯一的，對(duì)于一組解 x0,y0 則其所有解可以表示為 x=x0 b/gcd(a,b)*t,y=y0-a/gcd(a,b)*t,t=0, 1, 2……一般會(huì)要求找出 x 或者 y 的最小正整數(shù) 解，這個(gè)時(shí)候需要做一些調(diào)整。
• 總的來(lái)說(shuō)。遞歸是一來(lái)一回的過(guò)程，在gcd中，我們只用到了去的過(guò)程，求的最大公約數(shù)，而在exgcd中，我們發(fā)現(xiàn)了在來(lái)的過(guò)程中，某些數(shù)按照一定的規(guī)則變化，可以得到我們想要的結(jié)果而已。

static long x=0，y=0; ... static long extgcd(long a,long b){if(b==0) {x=1;y=0;return a;}long ans=extgcd(b, a%b);long team=x;x=y;y=team-a/b*y;return ans;}

求逆元：
從拓展歐幾里得中知道可以求ax by=c,一般是解決這類問(wèn)題
當(dāng)a，b互質(zhì)時(shí)候。c一定等于1.因?yàn)間cd（a,b）=1，c必須被gcd整除，那么如果有解一定是1.
那么ax by=1.
求逆元一般形式（求a關(guān)于1mod m的逆元）
ax≡1 (mod m). x就是所求的逆元
變形為 ax bm=1
這樣就可以運(yùn)用拓展歐幾里得（但是x要大于0處理）

static long x=0;static long y=0;//全局變量......long q=tgcd(a,b);// long x1=x;if(1%q!=0) {out.println("Not Exist");}else {while(x<=0){//x*a y*b=1 要求x>0這樣并且要求x最小，那么這樣操作就相當(dāng)于 ab-ab操作。剛開始還沒(méi)明白x =b;y-=a;}system.out.println(x);}//static long tgcd(long a,long b){if(b==0) {x=1;y=0;return a;}long ans=tgcd(b,a%b);long team=x;x=y;y=team-a/b*y;// System.out.println(x);return ans;}

還有用小費(fèi)馬可以求逆元，就不介紹了。

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的拓展欧几里得模板/求逆元模板（java）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。