查找非常大的数字

Question

分工的模我一定要找到这个数字的分工模：

239 ^（10^9）和10^9 + 13

239 ^（10^9）和10^9 + 15

...等等直到1001;

在C++中只使用本地库。怎么做？正如你所看到的，第一个数字是大约30亿个符号。

我试着找到模数周期的长度，但它们比10更长，甚至unsigned long long int也不能处理这么大的数字（239^10）。此外，我认为“大数”算法（将数字存储为数组）对我也不起作用（500 * 10^9）的操作太多。

顺便说一句，这应该工作少于5小时。

Answer 1

我们知道：

(A*B) % MOD = ((A % MOD) * (B % MOD)) % MOD 

所以

(A^n) % MOD = (((A^(n/2)) % MOD) * ((A^(n/2)) % MOD)) % MOD; 

我们可以递归地做到这一点。

所以，这里是我们的函数：

int cal(int pow, int val, int MOD){ 
    if(pow == 0) 
     return 1; 
    int v = cal(pow/2, val, MOD); 
    if(pow % 2 == 0) 
     return (v*v) % MOD; 
    else 
     return (((v*val) % MOD) * v) % MOD; 
}