C語言擴(kuò)展歐幾里得算法代碼

來源：本站原創(chuàng)|時(shí)間：2020-01-10|欄目：C語言|點(diǎn)擊：次

給定兩個(gè)正整數(shù)m和n,我們計(jì)算它們的最大公因子d和兩個(gè)整數(shù)a和b,使得a*m+b*n=d

算法流程
　　E1.置a'=b=1;a=b'=0;c=m,d=n;

　　E2.計(jì)算d和r,使得c=q*d+r;

　　E3.若r==0;則退出,當(dāng)前已有a*m+b*n=d;

　　E4;c=d;d=r;t=a';a'=a;a=t-q*a;t=b';b'=b;b=t-q*b;返回E2.

證明

　　對于已有的m和n,假設(shè)m>n;如果刨除變量a,b,a',b';算法與歐幾里得算法完全一樣,為計(jì)算最大公約數(shù)的算法.

　　最終要求的為a*m+b*n=d=GCD(m,n);如果改式子成立由歐幾里得算法可推出a'*n+b'*(m%n)=GCD(n,m%n);

　　因?yàn)镚CD(m,n)=GCD(n,m%n);

　　所以a*m+b*n=a'*n+b'*(m%n)

　　　　　　　　=a'*n+b'*(m-(m/n)*n)

　　　　　　　　=a'*n+b'*m-b'*(m/n)*n

　　　　　　　　=b'*m+(a'-b'*(m/n))*n

　　所以a=b';b=a'-b'*(m/n);

　　可以推出根據(jù)a‘、b'可以計(jì)算a、b。

代碼實(shí)現(xiàn)

復(fù)制代碼代碼如下:

void EGCD(int m,int n)
{
    int a,a1,b,b1,c,d,q,r,t;
    a1=b=1,a=b1=0,c=m,d=n;
    while(1)
    {
        q=c/d,r=c%d;
        if(r==0)
        {
            printf("(%d)*%d+(%d)*%d=%d\n",a,m,b,n,d);
            return;
        }
        c=d,d=r,t=a1,a1=a,a=t-q*a,t=b1,b1=b,b=t-q*b;
    }
}