引言

我们为什么会需要用到快速幂这种算法？试想这样一个场景:题目要求计算$254545565$的$2662313312$次幂。如果你还想用循环的方式从定义出发一个一个算，哎呦，你光这一步就得进行$2662313312$次运算，你不觉得太难受了吗？

二分快速幂

让我们试着用分治的思想去看待这个问题。如果指数是偶数，那么他除以2就是整数；如果指数是奇数，那么他减一除以2就是整数（这里废话）。那么就可以用如下思路进行转化
（图源英雄哪里出来）

递归思路

递归其实更直接一点，你只需要时时记得你写的函数意义是什么就好。设$f(x)=a^{b}modc$ 那么 $a^{(b-1)/2}modc$所以递归的代码我们就可以直接写出来

int qpow(int a, int b, int c)
{if (b == 0) return 1 % c;if (b % 2) return a * pow(qpow(a, (b - 1) / 2, c), 2) % c;else return pow(qpow(a, b / 2, c), 2) % c;
}

代码做一点小优化

int qpow(int a, int b, int c)
{if (b == 0) return 1 % c;int t = qpow(a, b / 2, c);if (b % 2 != 0) return a * t * t % c;return t * t % c;
}

(暂且不考虑比如$t\ast t$带来的溢出的问题）

二进制循环思路

让我们从二进制的角度来看问题。指数b的二进制表示为101010111…根据二进制数转换十进制数的方法，他就一定能表示为

(t1,t2,t3就是二进制表示中为1的数位）循环看每一位是不是1，是1就乘上底数a。a做出相应变化，即每循环一位就乘2。
这样int范围内最多也只会计算32次

LL qpow(LL a,LL b,LL c)
{if(b==0) return 1;long long res=1;while(b){if(b&1) res=res*a%c;a=a*a%c;b>>=1;}return res;
}

写在后面

我们再来好好看看两种看似不同的思路为什么其实是一种算法。首先是：$i>>=1$就是二进制右移一位，等价于$i/=2$，$b\&1$ 等价于$b\%2$，因为$b\&1$是在判断二进制表示的最后一位数字是几，而你会发现偶数的二进制表示的最后一位都是0，奇数都是1。这样看来，两种方式是不是就一样了？

课后习题

50. Pow(x, n)

题目链接
模板题，直接套上面的板子就好。注意处理b为负数的情况（如果太大取反可能会有溢出的情况，建议直接把b的类型定义为long）

递归

class Solution {double qpow(double a, long b){if (b == 0) return 1 ;if(b<0) b=-b;double t = qpow(a, b / 2);if (b % 2 != 0) return a * t * t;return t * t;}
public:double myPow(double x, int n) {if(n<0) return 1/qpow(x,n);return qpow(x,n);}
};

二进制

class Solution {double qpow(double a,long b){if(b==0) return 1;if(b<0) b=-b;double res=1;while(b){if(b&1) res=res*a;a=a*a;b>>=1;}return res;}
public:double myPow(double x, int n) {if(n<0) return 1/qpow(x,n);return qpow(x,n);}
};

372. 超级次方

b以数组的形式给出，九十八一个整数的十进制位分开了。哎咱们上面说的是二进制写快速幂呀，那十进制能不能按一样的思路来写？当然可以啦！$123^{1457}=123^{1000}\ast 123^{400}\ast 123^{50}\ast 123^7=(123^1{)}^{1000}\ast (123^4{)}^{100}\ast (123^5{)}^{10}\ast 123^7$，所以用一个数字来保存答案，循环每一位，让答案的十次方乘上下一位的次方数就好啦

class Solution {long qpow(long a,long b,long c){if(b==0) return 1;long res=1;while(b){if(b&1) res=res*a%c;a=a*a%c;b>>=1;}return res;}
public:int superPow(int a, vector<int>& b) {int res=1;for(int i=0;i<b.size();i++) res=qpow(res,10,1337)*qpow(a,b[i],1337);return res%1337;}
};

1808. 好因子的最大数目

数学太菜了，看到别人的代码中出现3是直接就懵了。。。还好有大佬一步一步写出来才解答了我这个菜鸡的疑惑。XingleiGao大佬的博客