[每日练习]最大公约数问题的推倒

最大公约数问题

描述：对于给定正整数x，y，求它们的最大公约数d，并且求出参数a, b使得ax+by=d

辗转相除法

最大公约数的编程求解一般采用辗转相除法，具体如下：

1.取x，y中的较大者，这里假设x>y。

2.用x对y取模（即mod运算），x % y = d.

3.如果d==0，则最大公约数为y；如果d!=0，则令x=y，y=d，继续第二步。

对于等式ax+by=d中a，b的求解方法，一般是在x，y辗转相除法的过程中递归得到的，具体如下。

假设在辗转相除法的倒数第二步中的x，y为x1，y1，x1 % y1 = d1 != 0。

然后采用上面第三步的方法令x2 = y1, y2 = d1，这时x2 % y2 = 0。说明y2就是我们求的最大公约数d。

这时我们令a2 = 0, b2 = 1，则a2 * x2 + b2 * y2 = d。

通过上面的推倒，我们知道x2 = y1, y2 = d1 = x1 % y1 = x1 – y1 * r (r = x1整除y1) 。

代入公式得到a2 * y1 + b2 * (x1 – y1 * r) = d = b2 * x1 + (a2 – b2*r) * y1 = d.

可以得出结论，a1 = b2, b1 = (a2 – b2*r) 。

转换为c代码如下

static int gcd(int x, int y, int *a, int *b){int q = x/y;int r = x%y;int d, a1, b1;if(r == 0){*a = 0;*b = 1;return y;}

d = gcd(y, r, &a1, &b1);*a = b1;*b = a1 – b1*q;return d;}

顺序推倒法

由上面的辗转相除法的推倒过程，我们可以得到启示。如果我们定义两个等式如下：

1 * x + 0 * y = x —————- (1)

0 * x + 1 * y = y—————- (2)

我们计算x/y，，令r = x / y，d = x % y = x – (r * y)。我们在上面两个等式的左右两边分别做计算，用上面等式的值 减去 下面等式乘以r。如下

(1 – 0 * r) * x + (0 – 1 * r) * y = x – r * y = d—————- (3)

这时候，对等式（2）和（3）做重复的操作，直到d==0。

转化为c代码如下：

static int FastGCD(int x, int y, int *a, int *b){int a1=1, b1=0, a2=0, b2=1;int q, tmp_a, tmp_b;int r = x%y;while((r = x%y)!=0){q = x/y;tmp_a = a1-q*a2;tmp_b = b1-q*b2;a1 = a2, b1 = b2, a2 = tmp_a, b2 = tmp_b;x = y;y = r;}*a = a2;*b = b2;return y;}

人，都有不能称心如意的时候，都有愿望落空的窘迫，