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 }
对于位运算熟的小盆友，还可以写成位运算形式，速度又快，又好理解
1 LL pow_mod(LL a, LL b){//a的b次方 2 LL ret = 1; 3 while(b){ 4 if(b & 1){ 5 ret = (ret * a) % MOD ; 6 } 7 a = (a * a ) % MOD ; 8 b >>= 1; 9 } 10 return ret; 11 }
这些知识到底算不算数论呢？？？不管了（´∀｀*)
ACM数论之旅2---快速幂，快速求a^b（(ノ｀Д´)ノ做人就要坚持不懈）
原文：http://www.cnblogs.com/linyujun/p/5199053.html