一、前言
快速幂（Exponentiation by squaring，平方求幂）是一种简单而有效的小算法，它可以公式的时间复杂度计算乘方。快速幂不仅本身非常常见，而且很多算法也都会用到快速幂。
二、问题分析
让我们先来思考一个问题：7的11次方，怎样算比较快？
1.普通解法
11次方不就是，11个7相乘吗？
这种算法我们需要运算11次，但这种算法比较耗时。
2.快速幂
如果我们将11转换成二进制就是：1011
7^11 =7^8∗7^2∗7^1
是不是和11的二进制彼此对应，当二进制为0是，跳过。
当二进制为1时，次方等于当前二进制1对应的十进制数字，快速幂只需计算3次。
下面以计算n的m次方为例：
定义base作为当前二进制为1对应的次方,ans为最终的结果值m向右移位，如果当前位是1，那么ans=ans*base; base=base*base，因为要计算二进制对应的十位数当m为0，输出结果
三、编码实现
typedeflonglongll;//定义long long型llquick_pow(lln,llm)//计算n的m次方{ llans=1,base=n;//初始化while(m!=0)//m不为0 { if(m&1)//当前为1ans=ans*base;//相乘base=base*base;//计数m=m>>1;//向右移位 } returnans;//输出结果}
四、总结与提高
了解了快速幂的用法之后，那就来做两道题巩固一下知识点吧。
