线性丢番图方程采用ax + by = c
. If是and这意味着c
的最大公约数,那么这就是Bézout 的恒等式a
b
a=z'c
b=z''c
与a=z'
和b=z''
方程有无数个解。因此,您可以检查是否c
是和的最大公约数(GCD)a
而b
不是试用搜索方法(在您的情况下,这转换为bx - dy = c - a
)
如果 确实a
和b
是c
then的倍数x
并且y
可以使用扩展欧几里得算法来计算,该算法找到满足 Bézout 恒等式的整数x
和y
(其中一个通常为负数)
你的答案是:
a = k*x
,
b = k*y
,
c - a = k * gcd(a,b)
对于任何整数k。
(附带说明:这也适用于任何其他欧几里得域,即多项式环和每个欧几里得域都是唯一的因式分解域)。您可以使用迭代方法找到这些解决方案:
迭代法
通过对同类项进行扩展和分组的常规代数(参考前面提到的维基百科文章的最后一节),得到以下迭代方法的算法:
- 1. 应用欧几里得算法,令 qn (n 从 1 开始) 是除法中商的有限列表。
- 2. 将 x0, x1 初始化为 1, 0,将 y0, y1 分别初始化为 0,1。
- 2.1 那么对于每个 i 只要定义了 qi,
- 2.2 计算 xi+1 = xi−1 − qixi
- 2.3 计算 yi+1 = yi−1 − qiyi
- 2.4 将 i 加 1 后重复上述操作。
- 3. 答案是 xn 和 yn 的倒数第二个。
伪代码:
function extended_gcd(a, b)
x := 0 lastx := 1
y := 1 lasty := 0
while b ≠ 0
quotient := a div b
(a, b) := (b, a mod b)
(x, lastx) := (lastx - quotient*x, x)
(y, lasty) := (lasty - quotient*y, y)
return (lastx, lasty)
因此,我编写了示例算法,该算法使用欧几里德算法迭代方法计算最大公约数,并且(对于负数 -需要这些额外步骤),它返回 GCD 并存储通过引用传递给它的变量的解决方案:a
b
x
y
int gcd_iterative(int a, int b, int& x, int& y) {
int c;
std::vector<int> r, q, x_coeff, y_coeff;
x_coeff.push_back(1); y_coeff.push_back(0);
x_coeff.push_back(0); y_coeff.push_back(1);
if ( b == 0 ) return a;
while ( b != 0 ) {
c = b;
q.push_back(a/b);
r.push_back(b = a % b);
a = c;
x_coeff.push_back( *(x_coeff.end()-2) -(q.back())*x_coeff.back());
y_coeff.push_back( *(y_coeff.end()-2) -(q.back())*y_coeff.back());
}
if(r.size()==1) {
x = x_coeff.back();
y = y_coeff.back();
} else {
x = *(x_coeff.end()-2);
y = *(y_coeff.end()-2);
}
std::vector<int>::iterator it;
std::cout << "r: ";
for(it = r.begin(); it != r.end(); it++) { std::cout << *it << "," ; }
std::cout << "\nq: ";
for(it = q.begin(); it != q.end(); it++) { std::cout << *it << "," ; }
std::cout << "\nx: ";
for(it = x_coeff.begin(); it != x_coeff.end(); it++){ std::cout << *it<<",";}
std::cout << "\ny: ";
for(it = y_coeff.begin(); it != y_coeff.end(); it++){ std::cout << *it<<",";}
return a;
}
通过将来自维基百科的示例传递给它a = 120
,b = 23
我们获得:
int main(int argc, char** argv) {
// 120x + 23y = gcd(120,23)
int x_solution, y_solution;
int greatestCommonDivisor = gcd_iterative(120, 23, x_solution, y_solution);
return 0;
}
r: 5,3,2,1,0,
q: 5,4,1,1,2,
x: 1,0,1,-4,5,-9,23,
y: 0,1,-5,21,-26,47,-120,
本示例的给定表格是什么: