之前一直知道扩展欧几里德算法的实现代码，但是原理一直还是模模糊糊，看了很多终于明白了，于是决定写一篇来记录下自己的思路。
下面实现的其他定理就不再多解释了，主要讲扩展欧几里德算法。
扩展欧几里德算法就是用来求 Ax+By=K 的一组解, A,B,K 都是已知常量，求解 x, y.
首先，根据“贝祖等式“可知，
Ax1+By1=gcd(A,B).
所以我们可以接着推出
C =A%B.
Bx2 + Cy2 = gcd(B,C)
= Bx2 + (A%B)y2 = gcd( B, A%B ).
然后我们再接着推个用到的
A%B=[A-(A/B)*B]. //这一步要注意下，这里的 ‘A/B’是计算机中的A/B，不保留小数的
最后，我们可以来总推了
Ax1 + By1 = gcd( A, B ) .
C=A%B.
Bx2 + Cy2 = gcd( B, C ).
gcd( A, B ) = gcd( B, C ).//划重点
所以
Ax1 + By1 = Bx2 + Cy2
Ax1 + By1 = Bx2 + ( A%B )y2
Ax1 + By1 = Bx2 + [ A - (A/B) * B ]y2
Ax1 + By1 = Bx2 + Ay2 - [ (A/B) *B]y2
根据恒等定理得
Ax1 = Ay2
By1 = Bx2 - B*[ (A/B) *y2 ] = B * [ x2 - (A/B)*y2 ]
所以
x1 = y2
y1 = x2 - (A/B)*y2
仔细观察下这其实就是个递推的过程
因为 x1要从 y2得来 , y1要从 x2 - (A/B)*y2得来
而 x2 要从 y3 得来 , y2要从 x3 - (A/B)*y3得来
.........................................................................
最终Xn-1 要从 Yn得来，Yn-1 要从 Xn - (A/B)*Yn
//注意，这里的A和B的值, 每次都不一样, A 和 B 不断的替换为 A=B , B=A%B,其实就是gcd的参数变换
那么这个递推的边界在哪里呢？
假设 A>0 B=0
则 gcd( A, B )=A.
则 Ax + By =gcd ( A,B )
可以推出 x=1, y=0.
那么边界就是当 B=0的时候, 赋值 x=1，y=0 然后返回
————————————————————————————————————————分割线————————————————————————————————————————
下面给出两个实现代码，一个是简单流程实现版，一个是代码简化版，建议看懂第一个 然后 用 第二个
//简化版 int gcd_pro(int A, int B, int &x, int &y){ if (B == 0) { x = 1; y = 0; return A; } else { int ans; int x_temp, y_temp; x_temp = x; y_temp = y; ans=gcd_pro(B, A%B, x_temp, y_temp); x = y_temp; y = x_temp - (A / B)*y_temp; return ans; }}
//白书版 int gcd_pro(int A, int B, int &x, int &y){ if (B == 0) { x = 1; y = 0; return A; } else { int ans; ans = gcd_pro(B, A%B, y, x); y -= (A / B)*x; return ans; }}
不过，我们经常性是要解决 Ax + By=C 这样的方程，知道了 Ax + By = gcd(A,B)的解又有什么用呢？
我们只要把 Ax + By = gcd(A,B) 得出的 x 和 y，
乘等于 C / gcd(A,B) 就得到 Ax + By = C 的解
下面给出例子
#include#include #include #include #include using namespace std;int gcd_pro(int A, int B, int &x, int &y){ if (B == 0) { x = 1; y = 0; return A; } else { int ans; ans = gcd_pro(B, A%B, y, x); y -= (A / B)*x; return ans; }}int main() { int ans; int x_ans, y_ans; int A_ans, B_ans, C_ans; x_ans = y_ans = 0; cin >> A_ans >> B_ans >> C_ans; ans=gcd_pro(A_ans, B_ans, x_ans, y_ans);
x_ans *= C_ans/ans;
y_ans *= C_ans/ans;cout << ans << endl << x_ans << ' ' << y_ans << endl; return 0;}