找出非常大数的除法模

Question

我必须找到这个数字的除法模数：

239^(10^9) 和 10^9 + 13

239^(10^9) 和 10^9 + 15

...等到 1001；

仅使用 c++ 中的本机库。怎么做？如您所见，第一个数字大约是 30 亿个符号。

我试着找出模周期的长度，但它们比 10 长得多，甚至 unsigned long long int 也无法处理这么大的数字 (239^10)。另外我认为 "big numbers" 算法（将数字存储为数组）对我也不起作用 (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;
}

找出非常大数的除法模

Find the modulo of division of very big numbers

c++

algorithm

modulo