寻找两个非常大的数字乘以一个非常大的数字的模数

Question

在编程练习中，我需要找出一个非常大的数字的模数，例如2提高到500000（最大输入数），其中1000000007为其他计算的一部分。

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

Answer 1

这是使用repeated squaring algorithm的绝佳时机。你可以计算x ^Ÿ（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 ，所以如果你的模数不是太大，你可以用简单的int来做计算。

希望这会有所帮助！

Answer 2

怎么样简单的东西像这样?:

#include <stdio.h> 

unsigned long PowMod(unsigned long p) 
{ 
    unsigned long prod; 

    if (p == 0) 
    return 1; 
    if (p == 1) 
    return 2; 

    prod = PowMod(p/2); 
    prod = (unsigned long long)prod * prod % 1000000007ULL; 
    if (p % 2 != 0) 
    { 
    prod = prod * 2 % 1000000007ULL; 
    } 

    return prod; 
} 

int main(void) 
{ 
    printf("%lu\n", PowMod(3)); 
    printf("%lu\n", PowMod(4)); 
    printf("%lu\n", PowMod(30)); 
    printf("%lu\n", PowMod(31)); 
    printf("%lu\n", PowMod(32)); 
    printf("%lu\n", PowMod(33)); 
    return 0; 
} 

输出（ideone）：

8 
16 
73741817 
147483634 
294967268 
589934536