扩展欧几里德算法（gcd扩展使用）数学

首先让我们先来普及一下，关于gcd的知识，这里几个字就可以搞定，gcd（a，b）就是指a，b的最大公约数，我靠，你可能会说这个有什么用呢？
不要着急，我们马上就会进行讲解:
首先先来普及一些基本概念：
首先他们必须满足贝祖等式（好高大上的名字啊！）： ax+by = gcd(a, b)。
于是由这个定理，我们成功推出了：（说实话我TM也没有听懂是怎么推的，呵呵！）
所以，我们由gcd函数的知识，可以成功的推出，如下两个递归时的方程：

ax+by=gcd(a,b); 因为a=a%b+(a/b)*b; 带入化简后：b((a/b)*x+y)+(a%b)*x=gcd(b,a%b);

下面为证明过程：

设：a>b。推理1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0; //------------------------------------------------------------- 推理2，ab!=0 时设 ax+by=gcd(a,b); //important bx1+(a%b)y1=gcd(b,a%b); 根据正常欧几里德原理有 gcd(a,b)=gcd(b,a%b); 则:ax+by=bx1+(a%b)y1; 因为a=a%b+(a/b)*b; 代入即:ax+by=bx1+(a-(a/b)*b)y1=ay1+bx1-(a/b)*by1=ay1+b(x1-(a/b)*y1); 由此得：x=y1 ,y=x1-(a/b)*y1; //------------------------------------------------------------- 这样我们就得到了求解 x,y 的方法：x，y 的值基于 x1，y1. \上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。

这个推理应该非常的完美了吧！
我认为这份推理很不错的诠释了我给lry讲了半天的东西是怎么来的（因为他设了两个变量），所以讲的非常清楚，点赞！
那么相信大家gcd应该是没有什么问题了：
下面是代码实现：

void gcd(int a,int b ,int &x,int &y) { if(b==0) { x=1; y=0; } else { gcd(b,a%b,x,y); int swap; swap=y; y=x-(a/b)*y; x=swap; } }

附件（网络资料）：
听说有非递归版！
http://anh.cs.luc.edu/331/notes/xgcd.pdf
http://math.cmu.edu/~bkell/21110-2010s/extended-euclidean.html
如果你还是没有看懂
下面有从《计算机程序设计艺术》转载的证明方法，仅供参考：

证明(1): 算法首次转到E2时，由上表，显然等式成立。步骤 E2，E3 并不会改变等式的正确性。所以只需要证明步骤 E4 不改变他们的正确性就可以了。执行 E4 之前， a'm + b'n = c(*) am + bn = d(**) 成立。 a'm + b'n = c = qd + r; a'm + b'n - q(am + bn) = r; (a' - qa)m + (b' - qb)n = r(***)执行 E4 之后，c←d, d←r, t←a', a'←a, a←t-qa, t←b', b'←b, b←t-qb; 所以 (**)变为 a' + b' = c (***)变为 am + bn = d 所以步骤 E4 不改变等式的正确性，得证。

下面强势给出非递归版代码：（我也好像有点懂！）

int exgcd(int m, int n, int &x, int &y) { if (n == 0) { x = 1; y = 0; return m; } int a, a1, b, b1, c, d, q, r, t; a1 = b = 1; a = b1 = 0; c = m; d = n; q = c/d; r = c%d; while (r) { c = d; d = r; t = a1; a1 = a; a = t - q * a; t = b1; b1 = b; b = t - q * b; q = c/d; r = c%d; } x = a; y = b; return d; }

（以上代码为转载）
相关练习题
P1082 同余方程
另一篇洛谷博客：
【扩展欧几里德算法（gcd扩展使用）】简单的欧几里德拓展