C語言 擴展歐幾里得算法代碼
更新時間：2013年09月01日 15:03:01 作者：
這篇文章介紹了擴展歐幾里得算法的實現(xiàn)代碼，有需要的朋友可以參考一下
給定兩個正整數(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,假設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;
}
}
相關文章
strcat函數(shù)與strncat函數(shù)的深入分析
本篇文章是對strcat函數(shù)與strncat函數(shù)進行了詳細的分析介紹，需要的朋友參考下2013-05-05
本文主要介紹了Qt處理焦點事件(獲得焦點,失去焦點)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-12-12
本文主要介紹C語言的二分查找算法,這里給大家詳細介紹了什么是二分查找,并提供代碼實例,需要的小伙伴可以參考下2016-07-07
c/c++拷貝構造函數(shù)和關鍵字explicit詳解
這篇文章主要介紹了c/c++拷貝構造函數(shù)和關鍵字explicit的相關知識，非常不錯，具有一定的參考借鑒價值,需要的朋友可以參考下2018-08-08
這篇文章主要為大家詳細介紹了C/C++如何實現(xiàn)磁盤相關操作,例如遍歷磁盤容量、實現(xiàn)磁盤格式化、移除指定磁盤等,感興趣的小伙伴可以跟隨小編一起學習一下2023-11-11
這篇文章主要為大家詳細介紹了opencv實現(xiàn)多張圖像拼接功能，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-01-01
淺談十進制小數(shù)和二進制小數(shù)之間的轉(zhuǎn)換
下面小編就為大家?guī)硪黄獪\談十進制小數(shù)和二進制小數(shù)之間的轉(zhuǎn)換。小編覺得挺不錯的現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-01-01
這篇文章主要為大家詳細介紹了C語言實現(xiàn)簡單的掃雷游戲操作，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-03-03
C++實現(xiàn)LeetCode(108.將有序數(shù)組轉(zhuǎn)為二叉搜索樹)
這篇文章主要介紹了C++實現(xiàn)LeetCode(108.將有序數(shù)組轉(zhuǎn)為二叉搜索樹),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07
雙向鏈表（Doubly Linked List）是一種常見的數(shù)據(jù)結構,在單鏈表的基礎上增加了向前遍歷的功能,與單向鏈表不同,雙向鏈表的每個節(jié)點除了包含指向下一個節(jié)點的指針外,還包含指向前一個節(jié)點的指針,本文給大家介紹了C語言中雙向鏈表的增刪改查2023-08-08