算法-如何快速找到系数x、y，使得d=xa+yb，其中d为a和b的最大公约数。

Question

最近遇到一个问题：如何快速找到整数系数x、y，使得d = xa + yb，其中d为a和b的最大公约数。发上来与大家讨论下，不要告诉我用枚举法啊。

Answer 1

首先按照@mario的方式，转换成已知两个互质的数a,b，有xa+by=1，求x,y。

95x + 26y = 1
利用辗转相除法,求得下列各式：

95 = 3 * 26 + 17 (1
26 = 1 * 17 + 9 (2
17 = 1 * 9 + 8 (3
9 = 1 * 8 + 1 (4
8 = 8 * 1 + 0 (5

下面根据上述各式求解

由(1知 17 = 95 - 3 * 26
由(2知 9 = 26 - 1 * 17
= 26 - 1 * (95 - 3 * 26)
= -95 + 4 * 26
由(3知 8 = 17 - 9
= (95 - 3 * 26) - (-95 + 4 * 26)
= 95 - 3 * 26 + 95 - 4 * 26
= 2 * 95 - 7 * 26
由(4知 1 = 9 - 8
= -95 + 4 * 26 - (2 * 95 - 7 * 26)
= -3 * 95 + 11 * 26

@mario 我用php写的，但愿你能看懂

<?php

// 求的ax + by = d(已知d为a/b公约数)

function calculate($a, $b, $d) {
// 化简为ax + by = 1
$a = $a / $d;
$b = $b / $d;
$d = 1;

// 运算各式 euclidean divisions
$exps = euclidean_divsions($a, $b);

// 初始化等式
$a_b_nums = array(
$a => array('a'=> 1, 'b'=>0),
$b => array('a'=> 0, 'b'=>1),
);

foreach($exps as $exp) {
$a_b_nums[$exp['rest']] = array(
'a' => $a_b_nums[$exp['dividend']]['a'] - $a_b_nums[$exp['divisor']]['a'] * $exp['quotient'],
'b' => $a_b_nums[$exp['dividend']]['b'] - $a_b_nums[$exp['divisor']]['b'] * $exp['quotient'],
);
if($exp['rest'] == $d) {
break;
}
}

// $a_b_nums的索引为$d的a的个数和b的个数就是x y的值
printf(" x = %d, y = %d时, {$a}x + {$b}y = $d 成立", $a_b_nums[$d]['a'], $a_b_nums[$d]['b']);
}

function euclidean_divsions($a, $b) {
$exps = array();

while($b != 0) {

// 计算表达式
$exp = array();
$exp['dividend'] = $a;
$exp['divisor'] = $b;
$exp['quotient'] = floor($a / $b);
$exp['rest'] = $a - $b * $exp['quotient'];
$exps[] = $exp;

// 下次计算的a和b
$a = $exp['divisor'];
$b = $exp['rest'];
}
return $exps;
}

calculate(95, 26, 1);

结果示例

![请输入图片描述]

Answer 2

可以通过在求取两个数a和b的最大公约数的过程中，保留对应的的商值，然后逆推，即可找到一对整系数x和y值。具体示例如下：

a b a/b a%b
51 33 1 18
33 18 1 15
18 15 1 3
15 3 5 0
3 0 - -

上述中，每一行是一次求解过程，a列存储比较大的原始数，b列存储比较小的原始数，a/b列存储两数之商，a%b存储两数的余数。
最后求的两数的余数之后，利用上述存储的值进行逆推。
对于上例，求得的最大公约数是d=3，那么逆推过程如下：
1.最后一行(3, 0, -, -)开始，x值是1，y值是0.因为此时a=3，已经与最大公约数相等了，所以直接令x=1，y=0，既可满足ax+by=d。
2.往上走一行。此时是(15, 3, 5, 0),此时x=y,y=x-(a/b)*y，其中等号右边的x和y分别是上一步求的的x和y的值，对于倒数第二行来说，也就是最后一行的x和y的值，即分别是1和0，那么此时x和y的值就分别是x=0，y=1.这时，这一行也满足。a=15,b=3,x=0,y=1，满足ax+by=d.
3.重复第2步，直至求到最开始的ab的那一行，求的x和y值就是满足条件的x和y值。
最终结果如下：

a b a/b a%b x y
51 33 1 18 2 -3
33 18 1 15 -1 2
18 15 1 3 1 -1
15 3 5 0 0 1
3 0 - - 1 0

综合表述，就是先从上往下通过取模计算出最大公约数，过程中保留商的值。然后再从下往上计算x和y的值。初始最下面x=1，y=0恒成立，然后按照x=y,y=x-(a/b)*y`的规律依次往上递推求取最开始的a,b值所对应的x和y的值。
这里解释一下原因。从一般性来讲，假设上述过程的的某两行如下：

 a b a/b a%b x y
b a%b ... ... x0 y0

上述过程第一行的a和b已知，可以求取a/b和a%b，x和y是待求变量。下一行是为了求取a和b的最大公约数而进行一次取模运算的结果，假设后面的x0和y0已知，现在想要求取x和y的值。对于这一步求取中无关的变量用...代表，例如上述第二行中的a/b和a%b值。
那么，对第二行公式化之后，就是：

 b * x0 + (a % b) * y0 = d (1)

现在为了求取x和y，我们可以这样逆推：

  a * x + b * y = d
a = (a / b) * b + a % b
-> ((a / b) * b + a % b) * x + b * y = d
-> (a / b) * b * x + (a % b) * x + b * y = d
-> ((a / b) * x + y) * b + (a % b) * x = d

将上述最后一个式子与已知式子(1)相比，等号左边前后两项分别对应，可知：

 (a / b) * x + y = x0
x = y0

然后就可以求出x和y分别是

 x = y0
y = x0 - (a / b) * x = x0 - (a / b) * y0

这样就可以通过下一行的x和y值逆推出上一行的x和y值。
而对于最后一行的x和y值肯定是已知的，即x = 1, y = 0，因为最后一行的a值一定就等于最大公约数d，而b值就是0。这样通过最后一行反推，一直到最开始的a和b值，就可以得到满足ax+by=d的x和y值了。

Answer 3

以前看过类似的问题，有关于裴蜀定理。
因为(a,b) = d。等式两边都除以d。
问题就转化成，已知两个互质的数a,b，有xa+by=1，求x,y。变成一个二元一次方程，具体怎么求，我也不会。
http://zhidao.baidu.com/question/107995660.html
求大神解答~。
裴蜀定理