文章/答案/技术大牛

发布

社区首页 >问答首页 >寻找非常大数的除法模

问寻找非常大数的除法模
EN

Stack Overflow用户

提问于 2015-05-14 18:07:14

回答 1查看 7K关注 0票数 2

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

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个小时起的作用要小。

c++

algorithm

modulo

回答 1

Stack Overflow用户

回答已采纳

发布于 2015-05-14 18:36:06

我们知道：

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

票数 6

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/30244306

复制

相似问题

问寻找非常大数的除法模
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问寻找非常大数的除法模EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问寻找非常大数的除法模
EN