a^b%p - wyiu - C++博客

C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合

:: 管理

posts - 100, comments - 15, trackbacks - 0

如果N是偶数，那么X^N =（X*X）^[N/2]；

如果N是奇数，那么X^N = X*X^(N-1) = X *（X*X）^[N/2]；

int powermod(int a, int b, int p)//a^b % p

{

if(b==0) return 1;

int t=powermod((a*a)%p, b/2, p);

if(b&1!=0) t=(t*a)%p;

return t;

}

int modexp(int a,int b, int p)

{

int t=1,;

while(b!=0)

{

if(b%2) t=(t*a)%p;

a=(a*a)%p;

b/=2;

}

return t;

}

posted on 2010-03-28 22:57 wyiu 阅读(114) 评论(0) 编辑收藏引用所属分类: 常用模板和函数

只有注册用户登录后才能发表评论。


相关文章: a^b%p 一日小结 KMP

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

随笔分类(84)