快速幂理论

· · 个人记录

这篇是给矩阵快速幂做基础的文章，我们来聊聊快速幂。

幂运算最浅显的算法就是循环了

这个地球人都会

int ans=1,k;
cin>>k;
for(int i=1;i<=n;i++){
    ans=ans*k;
}

这太简单了，而且比较起来，O(n)的时间，我们是有理由去接受这个复杂度的。

然而当我们对一个很大的底数，很大的指数的一个幂运算来讲，

这个O(n)的复杂度就显得不够好了。

有没有更优的方法进行幂运算呢？

当然有！！！

在说快速幂代码之前我们可以先分析一下，

然后我们可以看看十进制和二进制的转化。

1*（2^0）=1；

1*（2^1）=2；

0*（2^2）=0；

1*（2^3）=8；

显然，二进制每一位（0或1）依次乘2^n，∑x*（2^n）即为十进制的和。

另外一个显然的道理是2^n到2^（n+1）之间的所有数字，均可以用1,2,4,8...这些数字中一些数字的和来表示。

这样的话我们可以利用while循环

求出2^n

将目标幂运算分解为多个2^n的和。

这样的话对于一个幂运算我们可以减少其运算次数，

使他的复杂度为O（log n）

p.s.对于二进制我们可以用位运算来操作，每一位都是0或者1，乘以2^n累和。

int mi(int a,int b){//a^b 
    int ans=1;
    while(b){//b还有数字的时候循环
        if(b & 1==1) ans=ans*a;//如果b这一位是1，则转化为10进制（为0则跳过）
        a=a*a;//权重（计算2^n）
        b>>=1;//b右移一位
    }
    return ans;
}