C语言：欧几里得算法 or 辗转相除法

求最大公约数

#include <stdio.h> #include <math.h> int grd(int a, int b){ return (b ? grd(b, a % b) : a);//取余为0则返回前一个数，否则返回递归 } int main() { setvbuf(stdout, NULL, _IONBF, 0);//eclipce读写缓冲区问题 int a, b; while(~scanf("%d %d", &a, &b)){//要求a>b printf("the num is %d\n", grd(a, b)); } return 0; }

拓展的欧几里得定理

求ax + by = gcd(a, b)的唯一解a,b

这一组a, b是唯一的，就比如对a = 4, b = 2,无论怎么取，ax + by也只能是2的倍数，因为2是最小公倍数；同理若a = 5, b = 3， 可以得 -1 * 5 + 2 * 3 = 1 ，而1正是3,5的最小公倍数。

算法流程为先使用先前的递归算法得到gcd(a, b)的值，也就是最大公约数，然后因为递归的终止条件是a = gcd(a, b), b = 0， 此时有等式gcd(a, b) * 1 + 任意值 * 0 = gcd(a, b)，设任意值为0， 可得到此时的x, y有一组初始解x = 1, y = 0。

现在，为了求最初的x,y， 我们已知每一层的a,b值和前一层的x,y值，现在要求后一层的xy，自然想到使用递推式，通过前一层和后一层的两个方程，求出用前一层xy表示后一层xy的表达式。

这时纵观整个程序，已经递归到最深处，现在要从最深处返回到最初，求出a和b的值。由数学归纳法的思想方法，只要求出前一对xy与后一对xy之间的递推关系，就能得到后面任意的xy值，如下：

递归顺序算式后一组ax1 + by1 = gcd(a, b)前一组bx2 + (a % b)y2 = gcd(a, b)

注释： a % b = a - a / b * b 将前一组拆分得到 ay2 + b( x2 - a / b y2) = gcd(a, b) 按照后一组的分布格式，可以得到 x1 = y2 y1 = x2 - a / b y2 以上就是递推关系。 对于函数，我们则需要取出前一组的ab,xy，传给后一组的xy。

int gcd(int a, int b, int *x, int *y){ if (!b){ *x = 1; *y = 0; return a; } int xx, yy, ret = gcd(b, a % b, &xx, &yy); *x = yy; *y = xx - a / b * yy; return ret; } int main(){ int x, y; int a = 5, b = 3; printf("%d * a + %d * b = %d", x, y, gcd(a, b, &x, &y)); return 0; }