Java BigInteger实现扩展欧几里得算法递归出现除零错误如何解决

• 核心错误是扩展欧几里得算法的递归终止条件设置错误，未规避除数为0的计算场景
• 你的递归调用逻辑为gcd(q, p.remainder(q))，当递归到余数为0时，传入的第二个参数q会变为0，此时直接执行p.divide(q)就会触发ArithmeticException: BigInteger divide by zero异常
• 额外逻辑错误：原终止条件的返回系数不符合扩展欧几里得的推导规则，就算不触发除零异常也会得到错误的系数结果

修改gcd方法的终止判断逻辑和返回值即可，修复后的完整代码如下：

import java.math.BigInteger;

public class ExtGcdTest {
    public static void main(String[] args) throws Exception{
        BigInteger ex1 = new BigInteger("9");
        BigInteger ex2 = new BigInteger("13");
        BigInteger[] val = gcd(ex1,ex2);
        System.out.println("最大公约数d：" + val[0]);
        System.out.println("系数a：" + val[1]);
        System.out.println("系数b：" + val[2]);
    }

    // Returns a triple {d, a, b} such that d = a*p + b*q
    static BigInteger[] gcd(BigInteger p, BigInteger q) {
        // 调整终止条件：判断q是否为0，此时不需要做除法直接返回
        if (q.equals(BigInteger.ZERO))
            return new BigInteger[] { p, BigInteger.valueOf(1), BigInteger.valueOf(0) };
        BigInteger[] vals = gcd(q, p.remainder(q));
        BigInteger d = vals[0];
        BigInteger a = vals[2];
        BigInteger b = vals[1].subtract((p.divide(q)).multiply(vals[2]));
        return new BigInteger[] { d, a, b };
    }
}

运行上述代码输出为：

最大公约数d：1
系数a：3
系数b：-2

符合扩展欧几里得算法的推导结果，9*3 + 13*(-2) = 1，逻辑正确。

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