当前时区为 UTC + 8 小时



发表新帖 回复这个主题  [ 9 篇帖子 ] 
作者 内容
1 楼 
 文章标题 : 求教关于超大数的幂模运算怎么做?
帖子发表于 : 2010-06-20 13:30 

注册: 2010-06-20 13:28
帖子: 1
送出感谢: 0 次
接收感谢: 0 次
三个正整数a,n,p,

a<=10000,n<=10^10000,p<=100000000 。求a^n mod p。

这数的范围有点太大了。。特别是指数。。。 :em06


页首
 用户资料  
 
2 楼 
 文章标题 : Re: 求教关于超大数的幂模运算怎么做?
帖子发表于 : 2010-06-21 16:59 
头像

注册: 2008-02-24 14:15
帖子: 693
地址: 江苏
系统: Ubuntu
送出感谢: 17
接收感谢: 0 次
rlophous 写道:
三个正整数a,n,p,

a<=10000,n<=10^10000,p<=100000000 。求a^n mod p。

这数的范围有点太大了。。特别是指数。。。 :em06

用那个Long行吗?

一直到2147483647.

再长我就不会了.


_________________

怀念以前的老台式机。可惜现在租的地方没条件用了。目前只能用笔记本和手机了。


页首
 用户资料  
 
3 楼 
 文章标题 : Re: 求教关于超大数的幂模运算怎么做?
帖子发表于 : 2010-06-21 17:38 
头像

注册: 2007-09-29 3:09
帖子: 5777
送出感谢: 0 次
接收感谢: 5
欧拉定理,不解释...


_________________
HUNT Unfortunately No Talent...


页首
 用户资料  
 
4 楼 
 文章标题 : Re: 求教关于超大数的幂模运算怎么做?
帖子发表于 : 2010-07-01 21:14 
头像

注册: 2006-07-02 11:16
帖子: 12522
地址: 廣州
送出感谢: 0 次
接收感谢: 8
a^n = (a^(n/2))^2 (n 是偶数)

a^n = a * a^(n-1) (n 是基数)

算法复杂度 O(logn)


_________________
^_^ ~~~
要理解递归,首先要理解递归。

地球人都知道,理论上,理论跟实际是没有差别的,但实际上,理论跟实际的差别是相当大滴。


页首
 用户资料  
 
5 楼 
 文章标题 : Re: 求教关于超大数的幂模运算怎么做?
帖子发表于 : 2010-07-01 21:20 

注册: 2009-04-03 15:10
帖子: 1831
送出感谢: 0 次
接收感谢: 0 次
查数论书,关于模的运算可以化简,不过我忘了……可惜


页首
 用户资料  
 
6 楼 
 文章标题 : Re: 求教关于超大数的幂模运算怎么做?
帖子发表于 : 2010-07-02 0:17 

注册: 2007-05-25 5:59
帖子: 14
地址: Danmark
送出感谢: 0 次
接收感谢: 0 次
如果你用的是特定数(10,100,100...)你完全可以自己设计一个算法针对特定数字做,如果你是做随机整数,你可以用循环

long x=1;
for(int m=1;m<n;m++){
x=a*x;
y=mod(a,p); //求a^1与p的模
x=y; //只保留模
}

这个算法很容易证明


页首
 用户资料  
 
7 楼 
 文章标题 : Re: 求教关于超大数的幂模运算怎么做?
帖子发表于 : 2010-07-02 2:23 

注册: 2006-11-08 16:33
帖子: 286
送出感谢: 0 次
接收感谢: 0 次
HuntXu 写道:
欧拉定理,不解释...


哇,3楼好厉害,佩服佩服
哈哈,我给他解释,首先a和p都不大,所以可以因式分解对吧?a很小,所以因式分解出来也不复杂是吧?因此可以只考虑a是素数的情形。也就是说我们假定a,p互素。然后存在最小正整数d使得a^d=1(mod p),记为o(a),是a的阶。如果你能求出这个d,肯定就能化简了吧?ok,退一步,实际上你不需要这个d是最小的对吧,差不多就行了。d取\phi{p},即从1到p中与p互诉的整数个数,既然你已经把p因式分解了也就容易求得了吧?最后附上参考网页
http://zh.wikipedia.org/zh-hans/%E6%AC% ... 8%AE%BA%29


页首
 用户资料  
 
8 楼 
 文章标题 : Re: 求教关于超大数的幂模运算怎么做?
帖子发表于 : 2010-07-02 9:01 

注册: 2009-01-07 15:19
帖子: 153
送出感谢: 1
接收感谢: 0 次
这点东西都要祭出欧拉兄?欧老都要累死了....


4楼说的对,快速幂不解释。 :em05


_________________
大家好,我是计算机系大学生,玩电脑也 7.8 年了吧,可是这个系统为什么XXX,就不能XXX,连我这种XXX都XXX,怎么能够推广,看来XXX路还很长XXX,搞不懂你们这些XXX,再见了XXX


页首
 用户资料  
 
9 楼 
 文章标题 : Re: 求教关于超大数的幂模运算怎么做?
帖子发表于 : 2010-07-03 8:08 

注册: 2006-11-08 16:33
帖子: 286
送出感谢: 0 次
接收感谢: 0 次
afphoenix 写道:
这点东西都要祭出欧拉兄?欧老都要累死了....


4楼说的对,快速幂不解释。 :em05


很有道理, 毕竟用欧拉公式,最后两大数除法求余数也是要死人的, 由于n是已经k进制展开的所以快速幂一定很快


页首
 用户资料  
 
显示帖子 :  排序  
发表新帖 回复这个主题  [ 9 篇帖子 ] 

当前时区为 UTC + 8 小时


在线用户

正在浏览此版面的用户:没有注册用户 和 2 位游客


不能 在这个版面发表主题
不能 在这个版面回复主题
不能 在这个版面编辑帖子
不能 在这个版面删除帖子
不能 在这个版面提交附件

前往 :  
本站点为公益性站点,用于推广开源自由软件,由 DiaHosting VPSBudgetVM VPS 提供服务。
我们认为:软件应可免费取得,软件工具在各种语言环境下皆可使用,且不会有任何功能上的差异;
人们应有定制和修改软件的自由,且方式不受限制,只要他们自认为合适。

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
简体中文语系由 王笑宇 翻译