前言
快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高。
C++的实现方式：
先笔记一下：
|
1 2 |
b & 1 //取b二进制的最低位，判断和1是否相同，相同返回1，否则返回0，可用于判断奇偶（偶数二进制结尾是0奇数是1） b>>1 //把b的二进制右移一位，即去掉其二进制位的最低位 就是b=b/2 |
递归的方式
|
1 2 3 4 5 6 7 |
long long pow(long long a,long long b){ if (b==0) return 1; long long temp=pow(a,b>>1); temp=temp*temp%MOD; if (b&1) temp=temp*a%MOD; return temp%MOD; } |
非递归的方式
|
1 2 3 4 5 6 7 8 9 |
long long power(long long a,long long b){ long long t=1,y=a; while(b){ if (b&1==1) t=t*y%k; y=y*y%k; b=b/2; } return t; } |
