說(shuō)明了對(duì)任何整數(shù)a、b和它們的最大公約數(shù)d

關(guān)于未知數(shù)x和y的線性不定方程（稱(chēng)為裴蜀等式）：若a,b是整數(shù),且gcd(a,b)=d，那么對(duì)于任意的整數(shù)x,y,ax+by都一定是d的倍數(shù)

特別地，一定存在整數(shù)x,y，使ax+by=d成立

它的一個(gè)重要推論是：a,b互質(zhì)的充分必要條件是存在整數(shù)x,y使ax+by=1.

由此，我們便可對(duì)式子進(jìn)行化簡(jiǎn)

將同余式ax≡c(mod b)轉(zhuǎn)化為ax+by=c(很重要，做題列方程化簡(jiǎn)幾乎必定會(huì)用到，牢記)

充分必要條件也即充要條件，意思是說(shuō)，如果能從命題p推出命題q，而且也能從命題q推出命題p ，則稱(chēng)p是q的充分必要條件，且q也是p的充分必要條件。

樣例：

1 A=“三角形的三條邊都相等”；B=“三角形的三個(gè)角都相等”。

A是B的充分必要條件；

2 A=“某人觸犯了法律”；B=“應(yīng)當(dāng)依照刑法對(duì)他處以刑罰”。

A是B的必要不充分條件；（A觸犯法律包含各種法，有刑法有民法；B已經(jīng)確定是刑法。B屬于A所以A是B的必要不充分條件）

3 A=“付了足夠的錢(qián)”；B=“買(mǎi)到商店里的東西”。

A是B的必要不充分條件；（ A付夠了錢(qián) 可以買(mǎi)的是車(chē)、房子等；但是B能買(mǎi)到商店里的東西一定是要付夠錢(qián)）

ax1+by1=gcd(a,b)　　　ax2+by2=gcd(a,b)

可由此推出

ax1+by1=ax2+by2

a(x1-x2)=b(y2-y1)

因?yàn)間cd(a,b)為a,b的最大公因數(shù)，所以將 A=a/gcd(a,b)，B=b/gcd(a,b)，向下推出

A(x1-x2)=B(y2-y1)

此時(shí)A，B互質(zhì)，繼續(xù)向下推出

A(nB)=B(nA)

(x1-x2)=n*B

(y2-y1)=n*A

重點(diǎn)部分

這里從x入手，得

(x1-x2)=n*B

x1=x2+n*B

由此，我們推出了x解的通解公式 x=x0+n*B

同理，我們推出了y解的通解公式 y=y0-m*A

如果要求x的最小整數(shù)解,即x0,就為x0=x%B

如果我們要求的是 ax+by=c，還得先轉(zhuǎn)化 x=x*c/gcd(a,b).

然后套入公式

B=b/gcd(a,b)

x0=x%(b/gcd(a,b))

證畢(博主已累成狗，點(diǎn)個(gè)推薦唄) 若還不清楚，可移步Ta的博客(講的蠻詳細(xì)的)

int exgcd(int a,int b,int &x,int &y){if(b==0){x=1,y=1;return a;}int gcd=exgcd(b,a%b,y,x);//沒(méi)錯(cuò)，這玩意能求gcd    //不過(guò)c++是有系統(tǒng)函數(shù)求GCD的->__gcd(a,b);y-=a/b*x;return gcd;  }

(1).求解不定方程

(2).求解線性不定方程(線性同余方程)

(3).求解模的逆元

int exgcd(int a,int b,int &x,int &y){if(b==0){x=1,y=1;return a;}int gcd=exgcd(b,a%b,y,x);y-=a/b*x;return gcd;  }  int getinv(int a,int p){int x,y,gcd;gcd=exgcd(a,p,x,y);if(gcd==1){x=(x%p+p)%p;return x;}else{cout<<"a,p不互質(zhì)"<

#include  #define int long long  using namespace std;  int x=0,y=0;  int exgcd(int a,int b,int &x,int &y){if(b==0){x=1;y=0;return a;}int g=exgcd(b,a%b,y,x);y-=a/b*x;return g;  }  signed main(){int a,b;cin>>a>>b;exgcd(a,b,x,y);cout<<(x%b+b)%b;return 0;  }