欧几里得算法及其扩展欧几里得算法——数论数论

欧几里得算法（gcd）： 【欧几里得算法及其扩展欧几里得算法——数论】??又名辗转相除法，是求最大公约数的算法。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。两个数的最大公约数通常写成 gcd(a, b)。
例如，计算a = 1071和b = 462的最大公约数的过程如下：
??从1071中不断减去462直到小于462（可以减2次，即商q0 = 2），余数是147： 1071 = 2 × 462 + 147. 然后从462中不断减去147直到小于147（可以减3次，即q1 = 3），余数是21： 462 = 3 × 147 + 21. 再从147中不断减去21直到小于21（可以减7次，即q2 = 7），没有余数： 147 = 7 × 21 + 0. 此时，余数是0，所以1071和462的最大公约数是21。
由此可以得到算法：
递归：

int gcd (int n, int m) { if (m == 0) return n; else return gcd(m, n % m); }

迭代：

int gcd(int m,int n) { int t = 1; while(t != 0) { t = m % n; m = n; n = t; } return m; }

扩展的欧几里得算法（exgcd）： ??是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式 ax+by=gcd(a,b)
例子过程展示：
用类似辗转相除法，求二元一次不定方程47x + 30y = 1的整数解。

47 = 30 * 1 + 17
30 = 17 * 1 + 13
17 = 13 * 1 + 4
13 = 4 * 3 + 1

然后，把它们改写成“余数等于”的形式。

17 = 47 * 1 + 30 * (-1) ?? //式1
13 = 30 * 1 + 17 * (-1)????//式2
4 = 17 * 1 + 13 * (-1)?????//式3
1 = 13 * 1 + 4 * (-3)

然后，倒着计算并带入式子 1， 2， 3：

1 = 13 * 1 + 4 * (-3)
1 = 13 * 1 + 【17 * 1 + 13 * (-1)】 (-3)* ????//带入式 3
1 = 17 * (-3) + 13 * 4
1 = 17 * (-3) + 【30 * 1 + 17 * (-1)】 * 4 ??// 带入式 2
1 = 30 * 4 + 17 * (-7)
1 = 30 * 4 + 【47 * 1 + 30 * (-1)】 * (-7) ??//带入式 1
1 = 47 * (-7) + 30 * 11

得解 x = -7，y = 11。
代码实现：

int exgcd(int a, int b, int &x, int &y) { if(b == 0) { x = 1; y = 0; return a; } int r = exgcd(b, a % b, x, y); int t = x; x = y; y = t - a / b * y; return r; }