查找具有非常大数的两个非常大的数的乘法模数

Question

在编程练习中,我需要找出一个非常大的数的模数,例如2加到500000(输入的最大数),1000000007作为其他计算的一部分.

因为我可能需要多次发现,一种方法是创建一个5,00,000的数组.但它会阻塞大量的内存,所以我想知道有没有更好的方法来做到这一点？

Answer 1

这是使用重复平方算法的绝佳时机.您可以按如下方式计算x ^y(mod modulus):

int repeatedSquaring(int x, int y, int modulus) {
    if (y == 0) return 1;
    int val = repeatedSquaring(x, y / 2);
    val = (val * val) % modulus;

    if (y % 2 == 1) {
        val = (val * x) % modulus;
    }

    return val;
}

该算法仅需要O(log y)乘法和模数来计算.而且,每个中间值最多为modulus²,所以如果你的模数不是太大,你可以使用plain ints来进行计算.

希望这可以帮助!