负数的扩展欧氏算法

Question

在扩展欧氏算法的实现中，如何正确计算负数情况下的Bezout比系数？这是我的代码：

#include <iostream>
#include <cmath>
#include <tuple>

using namespace std;

tuple<int, int, int> xgcd(int a, int b, int s1 = 1, int s2 = 0, int t1 = 0, int t2 = 1) {
if (b == 0) {
return {abs(a), s1, t1};
}
int q = a / b;
return xgcd(b, a - q * b, s2, s1 - q * s2, t2, t1 - q * t2);
}

int main(double argc, char ** argv) {
tuple<int, int, int> result = xgcd(-10, -15);
cout << get<0>(result) << " " << get<1>(result) << " " << get<2>(result) << endl;

return 0;
};

在所提出的情况(-10，-15(中，GCD是正确计算的，但Bezout系数需要反转符号。处理它们的正确方法是什么？提前感谢！(

Answer 1

我解决了这个问题。解决方案是：在算法一开始就用它们的模块替换a和b。但是，Bezout的系数会被错误地找到。例如，设<0和b>0。然后在更改a的符号后，得到的Bezout的身份将如下所示：

gcd(a，b(=s(-a(+tb(根据-a和b(

或

gcd(a，b(=-sa+tb(根据a和b(。

一般来说，对于a和b任意符号，这将被写入

gcd(a，b(=sgn(a(sa+sgn(b(tb。

因此，如果我们改变a的符号，那么我们必须改变s的符号。类似地，如果我们更改b的符号，则我们必须更改t的符号。因此，递归形式的算法将写成：

tuple<int, int, int> xgcd(int a, int b, int sign_a = 0, int sign_b = 0, int s1 = 1, int s2 = 0, int t1 = 0, int t2 = 1) {
if (!sign_a) {
sign_a = a < 0 ? -1 : 1;
}
if (!sign_b) {
sign_b = b < 0 ? -1 : 1;
}
a = abs(a);
b = abs(b);
if (b == 0) {
return {a, sign_a * s1, sign_b * t1};
}
int q = a / b;
return xgcd(b, a - q * b, sign_a, sign_b, s2, s1 - q * s2, t2, t1 - q * t2);
}