一、题目背景
已知底数a，指数b，取模值mod。
求ans = a^b % mod
二、朴素算法（已知可跳过）
ans = 1，循环从 i 到 b ，每次将 ans = ans * a % mo
时间复杂度O(b)
void power(int a, int b, int mod){
ans = 1;
for (int i = 1; i <= b; i++) {
ans *= a;
ans %= mod;
}
} 三、快速幂算法
时间复杂度O(log2b)
最近看团队老师推荐的《算法竞赛（从入门到进阶）——罗勇军 郭卫斌著》一书，对快速幂算法有新的理解，之前分奇偶情况感觉理解不是很透彻。
以 2^11 为例，2^11 可分为 2^8 、 2^2 、2^1三项相乘，为什么指数11是分成8、2、1呢？熟悉二进制的人应该对这三个数很熟悉，分别的2^3, 2^1, 2^0。
恰是如此，在指数的分解上，我们可以把指数化为二进制。
（11）10 = （1011）2 = ( 2^3 + （0*2^2）2^1 + 2^0 )10 = 8 + 2 + 1
根据红色标红式可知，只有当二进制数字为1时，分解式中对应的项才是有效的（0乘任何数都为0）。
b&1：判断二进制最右边数字是否为1
b>>1：二进制数向右移一位
二者结合，判断二进制每次更新的最右位数字是否为1。
在快速幂算法中，a更新存储的是指数b从右往左的每一项（不管指数b最右是不是1，都在一直更新，例如2^0,2^1,2^2,2^3……）, 只有当b更新后的最右位是1，ans才会乘上a存储的项（可结合上面2^11的例子理解）
int qmod(int a, int b, int mod) {
int ans = 1;
a = a % mod;
while (b > 0) {
if (b&1) ans = (ans*a) % mod;
b = b >> 1;
a = (a*a) % mod;
}
return ans;
} 
京公网安备 11010502036488号