快速幂算法

如何计算，（n是正整数），只需要将a*a*a*a......*a，但它的时间复杂度为O(n)。

有什么办法可以快速解决这个问题，比如说：

先通过：

这个算法的本质是倍增原理

比如说，105=1+8+32+64，所以可以写成，将它展开

由于很容易计算，所以只需要将它们相乘就可以，但具体是如何实现的

可以看见105的二进制有四个1，而1，8，32，64的二进制只有一个1，根据这个思想写出伪代码：

计算

function BinExp(a,n)

r=1
while n!=0
    if n mod 2 ==1
        r = r * a
    a = a * a 

    n = [n/2]
return r

接下来看两道例题：

计算  mod m，

一个小公式：(a*b)%m = (a%m * b%m) %m