三个正整数a,n,p,
a<=10000,n<=10^10000,p<=100000000 。求a^n mod p。
这数的范围有点太大了。。特别是指数。。。
求教关于超大数的幂模运算怎么做?
-
- 帖子: 1
- 注册时间: 2010-06-20 13:28
- meteormatt
- 帖子: 693
- 注册时间: 2008-02-24 14:15
- 系统: Ubuntu
- 来自: 江苏
- 联系:
Re: 求教关于超大数的幂模运算怎么做?
用那个Long行吗?rlophous 写了:三个正整数a,n,p,
a<=10000,n<=10^10000,p<=100000000 。求a^n mod p。
这数的范围有点太大了。。特别是指数。。。
一直到2147483647.
再长我就不会了.
怀念以前的老台式机。可惜现在租的地方没条件用了。目前只能用笔记本和手机了。
- HuntXu
- 帖子: 5776
- 注册时间: 2007-09-29 3:09
- BigSnake.NET
- 帖子: 12522
- 注册时间: 2006-07-02 11:16
- 来自: 廣州
- 联系:
Re: 求教关于超大数的幂模运算怎么做?
a^n = (a^(n/2))^2 (n 是偶数)
或
a^n = a * a^(n-1) (n 是基数)
算法复杂度 O(logn)
或
a^n = a * a^(n-1) (n 是基数)
算法复杂度 O(logn)
^_^ ~~~
要理解递归,首先要理解递归。
地球人都知道,理论上,理论跟实际是没有差别的,但实际上,理论跟实际的差别是相当大滴。
要理解递归,首先要理解递归。
地球人都知道,理论上,理论跟实际是没有差别的,但实际上,理论跟实际的差别是相当大滴。
-
- 帖子: 1831
- 注册时间: 2009-04-03 15:10
Re: 求教关于超大数的幂模运算怎么做?
查数论书,关于模的运算可以化简,不过我忘了……可惜
-
- 帖子: 14
- 注册时间: 2007-05-25 5:59
- 来自: Danmark
- 联系:
Re: 求教关于超大数的幂模运算怎么做?
如果你用的是特定数(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; //只保留模
}
这个算法很容易证明
long x=1;
for(int m=1;m<n;m++){
x=a*x;
y=mod(a,p); //求a^1与p的模
x=y; //只保留模
}
这个算法很容易证明
-
- 帖子: 286
- 注册时间: 2006-11-08 16:33
Re: 求教关于超大数的幂模运算怎么做?
哇,3楼好厉害,佩服佩服HuntXu 写了:欧拉定理,不解释...
哈哈,我给他解释,首先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
-
- 帖子: 153
- 注册时间: 2009-01-07 15:19
Re: 求教关于超大数的幂模运算怎么做?
这点东西都要祭出欧拉兄?欧老都要累死了....
4楼说的对,快速幂不解释。
4楼说的对,快速幂不解释。
大家好,我是计算机系大学生,玩电脑也 7.8 年了吧,可是这个系统为什么XXX,就不能XXX,连我这种XXX都XXX,怎么能够推广,看来XXX路还很长XXX,搞不懂你们这些XXX,再见了XXX
-
- 帖子: 286
- 注册时间: 2006-11-08 16:33
Re: 求教关于超大数的幂模运算怎么做?
很有道理, 毕竟用欧拉公式,最后两大数除法求余数也是要死人的, 由于n是已经k进制展开的所以快速幂一定很快afphoenix 写了:这点东西都要祭出欧拉兄?欧老都要累死了....
4楼说的对,快速幂不解释。