负数场景下扩展欧几里得算法的贝祖系数计算问题

你的代码处理负数输入时，贝祖系数不符合要求的核心原因是base case未匹配返回的GCD符号：当递归到b=0时，你返回了abs(a)作为正的GCD，但此时的s1和t1满足的等式是a*s1 + b*t1 = a——如果a是负数，这个等式的结果是负数，和返回的正GCD矛盾，因此需要调整系数符号来匹配GCD的正负。

解决方案1：修正Base Case的系数符号 #

在递归终止的base case中，判断a的符号，若a为负则反转s1和t1的符号，确保最终满足a*s + b*t = abs(a)（即返回的GCD）。

修正后的代码：

#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) {
        int g = abs(a);
        int s = s1;
        int t = t1;
        // 当a为负数时，反转系数符号，使等式结果匹配正GCD
        if (a < 0) {
            s = -s;
            t = -t;
        }
        return {g, s, t};
    }
    int q = a / b;
    return xgcd(b, a - q * b, s2, s1 - q * s2, t2, t1 - q * t2);
}

int main(int argc, char ** argv) {
    tuple<int, int, int> result = xgcd(-10, -15);
    cout << get<0>(result) << " " << get<1>(result) << " " << get<2>(result) << endl;
    // 验证：-10*1 + (-15)*(-1) = -10 +15 = 5，与GCD一致
    return 0;
};

解决方案2：先转正数计算再调整系数 #

另一种更直观的方式是先将输入转为正数，用标准扩展欧几里得算法计算贝祖系数，再根据原数的符号调整系数，避免负数除法的歧义（C++中负数除法是截断向零，部分实现期望向下取整）。

示例代码：

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

using namespace std;

// 仅处理正数输入的扩展欧几里得实现
tuple<int, int, int> xgcd_pos(int a, int b, int s1 = 1, int s2 = 0, int t1 = 0, int t2 = 1) {
    if (b == 0) {
        return {a, s1, t1};
    }
    int q = a / b;
    return xgcd_pos(b, a - q * b, s2, s1 - q * s2, t2, t1 - q * t2);
}

// 包装函数，处理负数输入
tuple<int, int, int> xgcd(int a, int b) {
    int sign_a = a >= 0 ? 1 : -1;
    int sign_b = b >= 0 ? 1 : -1;
    auto [g, s_pos, t_pos] = xgcd_pos(abs(a), abs(b));
    // 调整系数符号，确保满足原数的贝祖等式
    int s = s_pos * sign_a;
    int t = t_pos * sign_b;
    return {g, s, t};
}

int main(int argc, char ** argv) {
    tuple<int, int, int> result = xgcd(-10, -15);
    cout << get<0>(result) << " " << get<1>(result) << " " << get<2>(result) << endl;
    // 验证：-10*(-2) + (-15)*1 = 20 -15 =5，与GCD一致
    return 0;
};

说明 #

贝祖系数本身不唯一，只要满足a*s + b*t = gcd(a,b)的解都是合法的，上述两种方式得到的系数只是不同的合法解。

内容的提问来源于stack exchange，提问作者Dave Bowman