詳細講解【拓展歐幾裡得】

exgcd（拓展歐幾裡得）

1.回顧輾轉相除法求最大公倍數： 

（輾轉相除法和下面所講到的算法裡面的m和n沒什麼關系可正可負 更沒有大小關系的區分）

  代碼：

#include<stdio.h>
int gcd(int a,int b)
{
    int temp;   
    if(b==0){
        return a;  // b=0 滿足關系跳出循環，此時a的值就是最大公約數
    }
    return gcd(b,a%b);

}
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    printf("%d\n",gcd(a,b));
    return 0;
}
           

2.exgcd：

a.求二進制一次方程的一組特解：

原理：

•ax+by=gcd(a,b)

•∵ gcd(a,b) = gcd(b,a%b)

•∴ ax1+by1 = bx2+(a%b)y2   //可以知道 a在被替換成了b，b被替換成了a%b 

•則 ax1+by1 = bx2+(a-a/b*b)y2

•∴ ax1+by1 = ay2+b(x2-a/b*y2)

•∴ x1=y2 y1=(x2-a/b*y2)   //這一步的x等于上一步的y，y等于(x2-a/b*y2)  x2 y2 代表上一步的x和y

•當b==0時，ax+by = gcd(a,b) = a

•∴ x=1 , y=0;
           

代碼：

#include<stdio.h>
int GCD;
int gcd(int a,int b,int &x,int &y)  //&x 類似于指針在c++函數調用中可以将x的值改變
{
    if(!b){               ②
        x=1;y=0;return a;       
    }                             //調用的函數運作順序
    GCD=gcd(b,a%b,y,x);   ①       //調用函數時的&不能加，錯誤不太容易發現  
    y-=a/b*x;             3 4 ...
    return GCD;                //最後傳回的GCD的含義其實就是a和b的最大公約數
}
int main()
{
    int a,b,x,y;
    scanf("%d%d",&a,&b);
    GCD=gcd(a,b,x,y);          
    printf("%d %d %d",x,y,GCD);
    return 0;
}
           

 b.求通解：

•ax + by = gcd(a,b)  的解集

•首先可以肯定它一定有解且解的數量無限

•我們可以找出式子可以加減的最小元 即最小公倍數lcm

•若x +- b/gcd y-+ a/gcd 則等式依然成立            //如果x後為+ 則y後為-

•便可得知解集
           

c.判斷ax+by=c是否有解:

        隻要c為gcd（a，b）的倍數，就有無數組結

例： 38x+8y=gcd(38,8)=2;               ①

        如果此時c=6 即：38x+8y=6； ②

  計算②式特解的方法：  先算出①式的特解 然後将x和y同時乘于6 / gcd（38，8）就能得到一組特解；

d.求最小整數解：

//用于解決ax+by=c類的求最小整數解  
GCD=exgcd(a,b);
x=c/GCD;           //如果非上面的類型而直接是=gcd(a,b) 可将這一步去掉即可
t=b/GCD:
if(t<0){
    t=-t;          //防止b/GCD為負數
}
x=(x%t+t)%t;
           

e.綜合例題：青蛙的約會（點選）

                     題解（點選）