原文链接：[传送门](http://www.cnblogs.com/linyujun/p/5199053.html) 膜拜大佬！！！

ACM数论之旅2—快速幂，快速求a^b（(ノ｀Д´)ノ做人就要坚持不懈）

 

a的b次方怎么求

pow（a, b）是数学头文件math.h里面有的函数

可是它返回值是double类型，数据有精度误差

 

那就自己写for循环咯

LL pow(LL a, LL b){//a的b次方 LL ret = 1; for(LL i = 1; i <= b; i ++){ ret *= a; } return ret; }

 

完美

 

 

可是题目是b的范围是1 <= b <= 1e9（＃°Д°）

超时，妥妥的。。。

 

 

 

看个例子

比如计算

2*2*2*2*2*2*2*2*2*2*2

可以这样算

原式=4*4*4*4*4*2

=8*8*4*2

=16*4*2

你看，相同的可以先合并，减少计算步骤

 

如果题目说数据很大，还需要求余，那么代码就可以这么写

1 LL pow_mod(LL a, LL b){//a的b次方 2 if(b == 0) return 1; 3 LL ret = pow_mod(a, b/2); 4 ret = ret * ret % MOD; 5 if(b % 2 == 1) ret = ret * a % MOD; 6 return ret; 7 }

 

这是递归写法

然后还有递推写法

 

1 LL pow_mod(LL a, LL b){//a的b次方 2 LL ret = 1; 3 while(b != 0){ 4 if(b % 2 == 1){ 5 ret = (ret * a) % MOD ; 6 } 7 a = (a * a ) % MOD ; 8 b /= 2; 9 } 10 return ret; 11 }

 

 

对于位运算熟的小盆友，还可以写成位运算形式，速度又快，又好理解，在加一个求余p，代码如下

 

 

1 LL pow_mod(LL a, LL b, LL p){//a的b次方求余p 2 LL ret = 1; 3 while(b){ 4 if(b & 1) ret = (ret * a) % p; 5 a = (a * a) % p; 6 b >>= 1; 7 } 8 return ret; 9 }

 

 

有了快速幂，于是，快速乘诞生了

1 LL mul(LL a, LL b, LL p){//快速乘，计算a*b%p 2 LL ret = 0; 3 while(b){ 4 if(b & 1) ret = (ret + a) % p; 5 a = (a + a) % p; 6 b >>= 1; 7 } 8 return ret; 9 }

 

 

(*´Д｀*)快速乘应该不怎么会用，无意义的东西，说不定哪天用的上

 

 

 

 

 

 

 

 

这些知识到底算不算数论呢？？？不管了（´∀｀*)

 

分类: 数论 好文要顶 关注我 收藏该文 镜外之主 关注 - 7 粉丝 - 96 +加关注 1 0 currentDiggType = 0; « 上一篇： ACM数论之旅1—素数（万事开头难（>_<）） » 下一篇： ACM数论之旅3—最大公约数gcd和最小公倍数lcm（苦海无边，回头是岸(￣∀￣)） posted @ 2016-02-18 18:43 镜外之主 阅读( 1074) 评论( 8) 编辑 收藏