求大数除法的模 [英] Find the modulo of division of very big numbers

问题描述

我必须找到这些数字的除法模:

I have to find the modulo of division of this numbers:

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

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

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

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

...以此类推，直到1001;

... etc up to 1001;

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

Using only native libraries in c++. How to do that? As you can see, the first number is about 3 billion symbols.

我试图找到模周期的长度，但是它们的模糊周期长于10，甚至unsigned long long int也无法处理这么大的数字(239 ^ 10).另外，我认为大数字"算法(将数字存储为数组)对我也不起作用(500 * 10 ^ 9)，这是太多操作.

I tried finding the length of modulo periods, but they are mush longer, than 10, and even unsigned long long int can't deal with such big numbers (239^10). Also I think that "big numbers" algorithms (storing a number as an array) will not work for me too (500*10^9) is too much operations.

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

BTW, this is supposed to work less, than in 5 hours.

推荐答案

我们知道:

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

所以

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

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

And we can do it recursively.

所以，这是我们的功能:

So, here is our function:

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;
}

这篇关于求大数除法的模的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！