java 中的模块 10^9+7

Question

我正在尝试对非常大的 long 数字使用模 10^9+7（或 1000000007），但我没有得到正确的结果。

long M = 1000000007;
int num = 212;
int val = 9;
long sol = (long)Math.pow(val,num) % M ; 

我应该得到输出

541416750(mod10^9+7)

但我得到的是

291172003

Answer 1

9¹²长溢出.

double Math.pow 也失去了精度，因此破坏了模值。 （如果一个 8 字节长的溢出，一个 8 字节的双精度值只能近似值，尤其是丢失最低有效数字。）

可以使用 BigInteger 作为直接的解决方案。

你也可以利用 a * b % n == ((a % n) * (b % n)) % n 来降低功率：

long modPow(int var, int num) {
    long m = 1;
    while (num > 0) {
        m = (m * var) % M;
        --num;
    }
    return m;
}

这不是最好的解决方案，但这个问题充满了数学和编程的味道 class， 因为模知识。

由于 M 是一个整数，return 值可以是一个转换的整数。