1樓：
歐幾里德演算法
歐幾里德演算法又稱輾轉相除法，用於計算兩個整數a,b的最大公約數。其計算原理依賴於下面的定理：
定理：***(a,b) = ***(b,a mod b)
證明：a可以表示成a = kb + r，則r = a mod b
假設d是a,b的乙個公約數，則有
d|a, d|b，而r = a - kb，因此d|r
因此d是(b,a mod b)的公約數
假設d 是(b,a mod b)的公約數，則
d | b , d |r ，但是a = kb +r
因此d也是(a,b)的公約數
因此(a,b)和(b,a mod b)的公約數是一樣的，其最大公約數也必然相等，得證
歐幾里德演算法就是根據這個原理來做的，其演算法用c++語言描述為：
void swap(int & a, int & b)
int ***(int a,int b)
if( 0 == b)
if(a > b)
int c;
for(c = a % b ; c > 0 ; c = a % b)
return b;
}模p乘法逆元
對於整數a、p，如果存在整數b，滿足ab mod p =1，則說，b是a的模p乘法逆元。
定理：a存在模p的乘法逆元的充要條件是***(a,p) = 1
證明：首先證明充分性
如果***(a,p) = 1，根據尤拉定理，aφ(p) ≡ 1 mod p，因此
顯然aφ(p)-1 mod p是a的模p乘法逆元。
再證明必要性
假設存在a模p的乘法逆元為b
ab ≡ 1 mod p
則ab = kp +1 ，所以1 = ab - kp
因為***(a,p) = d
所以d | 1
所以d只能為1
擴充套件歐幾里德演算法
擴充套件歐幾里德演算法不但能計算(a,b)的最大公約數，而且能計算a模b及b模a的乘法逆元，用c語言描述如下：
int ***(int a, int b , int& ar,int & br)
if(0 == b)
x1 = 1;
x2 = 0;
x3 = a;
y1 = 0;
y2 = 1;
y3 = b;
int k;
for( t3 = x3 % y3 ; t3 != 0 ; t3 = x3 % y3)
if( y3 == 1)
else
}擴充套件歐幾里德演算法對於最大公約數的計算和普通歐幾里德演算法是一致的。計算乘法逆元則顯得很難明白。我想了半個小時才想出證明他的方法。
首先重複拙作整除中的乙個論斷：
如果***(a,b)=d，則存在m,n，使得d = ma + nb，稱呼這種關係為a、b組合整數d，m，n稱為組合係數。當d=1時，有 ma + nb = 1 ，此時可以看出m是a模b的乘法逆元，n是b模a的乘法逆元。
為了證明上面的結論，我們把上述計算中xi、yi看成ti的迭代初始值，考察一組數(t1,t2,t3)，用歸納法證明：當通過擴充套件歐幾里德演算法計算後，每一行都滿足a×t1 + b×t2 = t3
第一行：1 × a + 0 × b = a成立
第二行：0 × a + 1 × b = b成立
假設前k行都成立，考察第k+1行
對於k-1行和k行有
t1(k-1) t2(k-1) t3(k-1)
t1(k) t2(k) t3(k)
分別滿足：
t1(k-1) × a + t2(k-1) × b = t3(k-1)
t1(k) × a + t2(k) × b = t3(k)
根據擴充套件歐幾里德演算法，假設t3(k-1) = j t3(k) + r
則：t3(k+1) = r
t2(k+1) = t2(k-1) - j × t2(k)
t1(k+1) = t1(k-1) - j × t1(k)
則t1(k+1) × a + t2(k+1) × b
=t1(k-1) × a - j × t1(k) × a +
t2(k-1) × b - j × t2(k) × b
= t3(k-1) - j t3(k) = r
= t3(k+1)
得證因此，當最終t3迭代計算到1時，有t1× a + t2 × b = 1，顯然，t1是a模b的乘法逆元，t2是b模a的乘法逆元。
2樓：
應該是遞迴演算法了。佩服樓上的
vb程式設計用歐幾里得演算法求倆個正整數的最大公約數
3樓：咫尺而天各一方
private sub form_click()dim m%, n%, t%, i%, r%m = inputbox("請輸入bai一du個zhi數dao字m")
n = inputbox("請輸入乙個數字n")if m < n then t = m: m = n: n = tr = n
do while n > 0 and m > 0 and r <> 0
r = m mod n
m = n
n = r
loop
print "m,n的最大專公約數為
屬"; m
end sub
c語言程式設計 求兩個數的最大公約數和最小公倍數 描述： 用輾轉相除法（即歐幾里得演算法）求兩個正整數的最大
4樓：匿名使用者
#include
void main()
rem=d/div;
printf("%d\n",rem);}
5樓：匿名使用者
#include
void main()
6樓：瑞來鮮于千兒
這樣寫：
#include
void
main()
i=n;
while(i%m!=0)
printf("最小公倍數是:%d
\n",i);
r=m%n;
while(r!=0)
printf("最大公約數是:%d
\n",n);}圖：
用歐幾里得演算法（輾轉相除法）求最大公約數,c語言程式設計
7樓：猴大俠來也
你的程式是正確的，
瑕疵在於
scanf("%d,%d",&m,&n);
scanf函式，雙引號內光寫格式就好了，不用寫逗號什麼的，多寫什麼程式執行的時候就要輸入什麼。如你所寫，執行時就應輸入：12，24 若你在12與24之間按的是空格或其他有可能影響到第二個變數取不到值。
所以建議改為
scanf("%d%d",&m,&n); 程式執行要求輸入時兩個數之間按空格回車隨你。
8樓：匿名使用者
if(m r=m; m=n; n=r; 這裡缺了點什麼 改if（m 認同求採納，求經驗，求懸賞 不認同可以問，有求必應 9樓：匿名使用者 刪掉if(m r=m; m=n; n=r;就好了 用歐幾里得演算法求最大公約數，求大神指導錯誤，好像有邏輯錯誤。。。。 10樓：匿名使用者 最後應該是while（r!=0) 11樓：聽不清啊 /*函式定義*/ int *** ( int x , int y )while(r!=0); }return x;} 12樓：匿名使用者 有無問題可以通過測試出來~ 用歐幾里得演算法求出（－1859，1573），（30，45，84），（2n-1，n-2）的最大公約數
150 13樓：愛 解：（－1859，1573） =（1859,1573） =（286,1573） =（286,1573-286*5） =（286,143） =（0,143） =143 （30，45，84） =（30,15,84）=（0,15,84） =（15,84） =（15,15*6-84） =（15，-6） =（3,6） =3（2n-1，n-2） =（2n-1-2(n-2),n-2） =(3,n-2) 打字不容易，望採納。。。 由題意,當抄m,n都是正奇數時,m 襲n m n 當m,n不全為bai正奇數時 du,m n mn 若a,b都是正奇數,則由zhia b 16,可得daoa b 16,此時符合條件的數對為 1,15 3,13 15,1 滿足條件的共8個 若m,n不全為正奇數時,m n mn,由a b 16,可得ab... 1.11 12 132 2.11 13 143 3.6 2 8 2 10 2 200 3.1000 1 x 2 490 x 30 4.x 6 x 6 1 1260 x 5.x x 1 300 2 x 25 1 x x 1 132 x 11，兩個數是11，122 x x 1 143 x 11 兩個數是... 什麼時候要，我可以寫 如何用vb設計乙個程式，隨機產生二十個三位整數 sub s randomize 初始化隨機變數 for i 1 to 20 做20次迴圈debug.print int 100 rnd 900 輸出隨機數到立即視窗 next end sub 樓上連陣列都沒有定義，也沒有把產生的數...對於任意兩個正整數m,n,定義某種運算法則如下當m
以知兩個連續整數積為132，求這兩個數
vb程式設計題 隨機產生兩個2位整數，使用choose函式隨機產生操作符給使用者出一道算