Python实现GCD工具遇负数返回负值问题求助（禁用abs/math库）

你的GCD工具在输入负数时返回负值，核心问题出在两个地方：一是初始的大小交换逻辑在负数场景下干扰了算法流程，二是扩展欧几里得算法的公式实现有误，加上最终没有处理结果的符号。以下是修正后的方案，完全符合作业要求（不使用abs()或math库）：

修正后的代码 #

from sys import stdin


a = 0
b = 0
a0 = 0
b0 = 0
a1 = 0
b1 = 0
n = 0
na = 0
nb = 0
q = 0

for line in stdin:
    input = line.lstrip().rstrip().split()

    if line == '' or len(input) != 2:
        break

    a, b = [int(x) for x in line.lstrip().rstrip().split()]

    # 移除错误的大小交换逻辑，负数场景下的大小比较会打乱欧几里得算法流程
    # if a > b:
    #     a, b = b, a


    a0 = 1
    b0 = 0
    a1 = 0
    b1 = 1

    # 用整数除法//替代浮点数除法/，避免后续计算出错
    n = a % b
    q = a // b

    na = a0 - q * a1
    nb = b0 - q * b1
    
    a = b
    a0 = a1
    b0 = b1
    

    b = n
    a1 = na
    b1 = nb
    


    while n != 0:
        n = a % b
        q = a // b
        
        # 修正扩展欧几里得算法的公式，用减号替代加号
        na = a0 - q * a1
        nb = b0 - q * b1

        a = b
        a0 = a1
        b0 = b1

        b = n
        a1 = na
        b1 = nb
   
    # 手动处理结果符号：若为负则输出相反数，不使用abs()
    print(-a if a < 0 else a)

关键修改点 #

• 移除错误的交换逻辑：原来的if a > b交换在负数场景下（比如-888和-2）会错误地保留顺序，干扰算法的取模流程，欧几里得算法本身不需要预先确保两个数的大小关系。
• 修复除法运算：把q = a / b改成q = a // b，避免浮点数参与整数运算导致的精度问题。
• 修正扩展欧几里得公式：循环内的na = a0 + q * a1改为na = a0 - q * a1，符合算法的数学推导。
• 手动调整结果符号：最后通过条件判断-a if a < 0 else a将负数结果转为正数，完全符合GCD的定义，且未使用abs()或math库。

验证预期输入输出 #

Input       Output

7 11        1
888 2       2
905 5       5
-7 11       1
-888 -2     2
905 -5      5

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