0 
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 的数字，它会给出负数作为输出。无法弄清楚出了什么问题。

4

2 回答 2

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 63，所以你的代码溢出了 Java 的范围long。

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

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

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

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

和

return (((n % mod) * ((result * result) % mod) % mod);
于 2014-08-04T19:23:53.660 回答
1 
But it gives negative numbers as output for numbers greater than 10

那是因为你已经达到了positive overflowlong 因此返回/从负溢出开始。

long 的值范围从minimum value of -2^63 and a maximum value of 2^63-1您到达2^63-1它时开始，然后返回-2^63并从那里开始。

于 2014-08-04T18:28:22.550 回答