幂求余 - 编程论坛

#2

yaiby2007-11-11 22:49

x^n%m=(x%m)^n
应该对吧。。。

#3

拉风2007-11-11 23:13

m>x时，楼上的式子明显不成立

#4

yaiby2007-11-11 23:18

是哈没考虑M>X时代情况～～
呵呵～

#5

nuciewth2007-11-12 16:25

(a*b)%m==((a%m)*(b%m))%m

#6

neverDie2007-11-12 19:07

是a^b不是a*b

#7

lyixh2007-11-12 19:59

x^n是不是x的n次方哦？
int i;
long sum=1;
for(i=0;i<n;i++)
sum=sum*x;
y=sum%m;

#8

neverDie2007-11-12 20:53

以下是引用lyixh在2007-11-12 19:59:16的发言：
x^n是不是x的n次方哦？
int i;
long sum=1;
for(i=0;i<n;i++)
sum=sum*x;
y=sum%m;

x,n,m<999

你这样显然益出

#9

nuciewth2007-11-12 23:12

以下是引用neverDie在2007-11-12 19:07:37的发言：
是a^b不是a*b

老兄,你不知道幂是由积而来的吗?

#10

duccdd2007-11-13 07:00

由(a*b)%m=((a%m)*(b%m))%m
得x^n%m=(...(((x%m)*(x%m))%m*(x%m))...*(x%m))
令x%m=b
则x^n%m=b*b%m*b%m*b%m...

#11

HJin2007-11-13 09:51

/** This functions returns b^e mod m
b --- base
e --- exponent
m --- mod
*/
int ModularExponentiation(int b, int e, int m)
{
int r = 1;

b %= m;
while(e)
{
if(e&1)
r=(r*b)%m;
b=(b*b)%m; // may overflow
e>>=1;
}

return r;
}

#12

lyixh2007-11-14 11:48

以下是引用neverDie在2007-11-12 20:53:59的发言：

x,n,m<999

你这样显然益出

把int 改成long就是了撒

#13

雨中飞燕2007-11-14 12:11

楼上不知道在win32下，int和long的长度是一样的吗？

by 雨中飞燕 C/C++学习讨论群:46520219
[url=http://yzfy.org/]C/C++算法习题(OnlineJudge)论坛：[/url] http://yzfy.org/blog/blog.php?uid=2

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url] [url=http://blog.programfan.com/article.asp?id=24801]请不要写出非int声明的main函数[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=181314" target="_blank">https://yzfy.org/bbs/
Blog: http://yzfy.org/blog/blog.php?uid=2

[url=http://bbs.bc-cn.net/viewthread.php?tid=163571]请大家不要用TC来学习C语言，点击此处查看原因[/url] [url=http://blog.programfan.com/article.asp?id=24801]请不要写出非int声明的main函数[/url]
[url=http://bbs.bc-cn.net/viewthread.php?tid=181314]C++编写的Windows界面游戏[/url]