用于计算模逆运算的 Java 程序输出大于 10 的数字的负值

Question

import java.util.*;  
class ModuloInverse {
    static long mod = 1000000007;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long num = in.nextLong();
        System.out.println(m_inverse(num, mod));
    }
    static long m_inverse(long a, long p) {
        return m_pow(a, p - 2);
    }
    static long m_pow(long n, long m) {
        long result = 0;
        if (m == 1) {
            return (n % mod);
        }
        if (m % 2 == 0) {
            result = m_pow(n, m / 2);
            return ((result * result) % mod);
        } else {
            result = m_pow(n, (m - 1) / 2);
            return (((n % mod) * (result * result)) % mod);
        }
    }
}

这是我编写的用于计算乘法模逆(模 10^9+7(的 Java 程序。但它给出负数作为大于 10 的数字的输出。不知道出了什么问题。

Answer 1

我在底部的if语句中添加了几行调试行：

    if (m % 2 == 0) {
        result = m_pow(n, m / 2);
        System.out.println("m = " + m + ", result = " + result + ", returning " + ((result * result) % mod));
        return ((result * result) % mod);
    } else {
        result = m_pow(n, (m - 1) / 2);
        System.out.println("m = " + m + ", n % mod = " + (n % mod) + ", result = " + result + ", returning " + (((n % mod) * (result * result)) % mod));
        return (((n % mod) * (result * result)) % mod);
    }

当我使用值 13 运行它时，这是打印出的最后一行：

m = 1000000005，n % mod = 13，结果 = 846153852，返回 -428497853

现在846153852 × 846153852 × 13> 2⁶³，因此您的代码超出了 Java long的范围。

mod是 10⁹ + 7，如果result介于 0 和 mod 之间，那么result * result不会超过 10 18，肯定小于 1.1 × 10¹⁸。 long可以保持的最大正值约为 9.2 × 10¹⁸，因此一旦n爬升到约 9 以上，result * result * n就有可能超过该值。 据我所知，这首先发生在n = 13.

两个数的乘积模mod永远不会超过Java long的范围，但三个或更多数的乘积可能会超过。

解决此问题的一种方法是更换行

return (((n % mod) * (result * result)) % mod);

跟

return (((n % mod) * ((result * result) % mod) % mod);

Answer 2

But it gives negative numbers as output for numbers greater than 10

那是因为你已经到了多头的positive overflow，因此回到/从负溢出开始。

Long 的这个值的范围从 minimum value of -2^63 and a maximum value of 2^63-1 到你达到2^63-1然后它会回到-2^63并从那里开始。