C語言 擴展歐幾里得算法代碼
給定兩個正整數(shù)m和n,我們計算它們的最大公因子d和兩個整數(shù)a和b,使得a*m+b*n=d
算法流程
E1.置a'=b=1;a=b'=0;c=m,d=n;
E2.計算d和r,使得c=q*d+r;
E3.若r==0;則退出,當前已有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';算法與歐幾里得算法完全一樣,為計算最大公約數(shù)的算法.
最終要求的為a*m+b*n=d=GCD(m,n);如果改式子成立由歐幾里得算法可推出a'*n+b'*(m%n)=GCD(n,m%n);
因為GCD(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'可以計算a、b。
代碼實現(xiàn)
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;
}
}
相關(guān)文章
strcat函數(shù)與strncat函數(shù)的深入分析
本篇文章是對strcat函數(shù)與strncat函數(shù)進行了詳細的分析介紹,需要的朋友參考下2013-05-05c/c++拷貝構(gòu)造函數(shù)和關(guān)鍵字explicit詳解
這篇文章主要介紹了c/c++拷貝構(gòu)造函數(shù)和關(guān)鍵字explicit的相關(guān)知識,非常不錯,具有一定的參考借鑒價值,需要的朋友可以參考下2018-08-08C/C++實現(xiàn)磁盤相關(guān)操作的示例代碼
這篇文章主要為大家詳細介紹了C/C++如何實現(xiàn)磁盤相關(guān)操作,例如遍歷磁盤容量、實現(xiàn)磁盤格式化、移除指定磁盤等,感興趣的小伙伴可以跟隨小編一起學習一下2023-11-11淺談十進制小數(shù)和二進制小數(shù)之間的轉(zhuǎn)換
下面小編就為大家?guī)硪黄獪\談十進制小數(shù)和二進制小數(shù)之間的轉(zhuǎn)換。小編覺得挺不錯的現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2017-01-01C++實現(xiàn)LeetCode(108.將有序數(shù)組轉(zhuǎn)為二叉搜索樹)
這篇文章主要介紹了C++實現(xiàn)LeetCode(108.將有序數(shù)組轉(zhuǎn)為二叉搜索樹),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07