**对于正整数 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; } ~~~