引入：
普通幂运算：\(a^b\) 及连续乘以\(b\)次\(a\).
显然，效率很TM低
首先，我们要知道，
\(x^y=x^ {y_1+y_2+...+y_n }\) 例如，当
\(b=11\)时， 位权时最大的基本单位，他们可以拼成一定范围内的所有数，故二进制拆分是最快的，多重背包的优化也是这种思想。 将
\(b\)拆成2进制，则
\(b=(1011)_2=(1×2^3+0×2^2+1×2^1+1×2^0)_{10}\) 所以
\(a^b=a^{2^3+2+1}\) 代码：
#include<cstdio>
inline int quick_pow(int A , int B){
int base = A, ans = 1;
while(B){
if(B & 1){//取B的末尾进行算位权
ans *= base;
}
base *= base;//及base=base^2,因为每次次数要按位加一
B >>= 1;//去掉一位
}
return ans;
}
int main(){
int a , b;
scanf("%d%d",&a , &b);
printf("%d",quick_pow(a , b));
return 0;
}
转载于:https://www.cnblogs.com/defense/p/11609905.html
