**對于正整數 a和b ?利用歐幾里得算法可以得出 一個最大公因數 , ?改進后的算法滿足 ?最大公因數 q=xa+yb ? ;** **那么我們如何求出 a和b呢 。** **書上是這么寫的 那么我們用代碼把他實現出來, 向大家推薦一本書《The Art Of Computer.Programmer》 ? 第一篇的數學部分 ? 真心的枯燥 我選擇的方式 是 適當的囫圇吞棗 對于這一樣 ,但是對于其中講述的算法 還是要仔細的去看滴 。**  **對于算法的分析 ?我直接上原書圖**  ~~~ #include "stdafx.h" //擴充的歐幾里得算法 //對于正整數 a,b 有 m*a+n*b=r //r 為最大公約數 這就是改進后的歐幾里得算法 int _tmain(int argc, char**grav) { int m = 1000, n = 255; int r; int t; int x = 0, x1 = 1, y1 = 0, y = 1; while ((r = m%n) != 0) { //改變x x1 t = x1; x1 = x; x = t - (int)(m / n)*x; //改變y y1 t = y1; y1 = y; y = t - (int)(m / n)*y; //改變 m<-n n<-r m = n; n = r; } printf("x=%d,y=%d,余數=%d", x,y,n); return 0; } ~~~