关于快速幂……

短命女 2021-12-19 04:51 273阅读 0赞

> **写在前面**
> 
> 这是一个基础不太扎实的蒟蒻的随手整理内容……
> 
> 主要分为两部分吧
> 
> 1.普通快速幂
> 
> 2.矩阵快速幂
> 
> **题目完成进度**

当我们要求(ab)mod n的结果时，暴力的话就是直接循环b次把底数a相乘再mod n，这样的时间复杂度是O(b)的，但如果b的取值很大，效率就不高了，因此我们就需要优化。

如何优化呢？当然是用快速幂啦！(感觉我好蠢啊QAQ)

> **一.普通快速幂**

**1.思路解析**

对于线性求解的问题，如果需要优化，基本就是考虑树形结构或者分治，把原本O(n)的复杂度降到O(logn)，这里的快速幂用到的就是分治思想

现在要求ab，那么有两种情况，我们分别对这两种情况进行不同的转化：

<1>b为偶数，则**ab=ab/2\*ab/2**

<2>b为奇数，则**ab=ab/2\*ab/2\*a**(b/2向下取整)

这样以此类推，把b/2继续分解成b/4，b/8……最终直至b被分解为1，这样的算法就叫快速幂算法

**2.核心代码**

int ksm(int a,int b,int n){
        if(b==1) return a;
        if(b%2==0){
        //如果b是偶数
            int t=ksm(a,b/2,n);
            return t*t%n;
        }
        else{
        //如果b是奇数
            int t=ksm(a,b/2,n);
            t=t*t%n;
            t=t*a%n;
            return t;
        }
    }

以上是递归形式的写法，如果写成非递归形式就是下面酱紫QWQ

int ksm(int a,int b,int n){
        int res=1;
        while(b){
            if(b%2==1) res=res*a%n;//如果是奇数就要记得多乘一个底数
            a=a*a%n;//因为指数变成了原来的一半，所以底数要变成原来的平方
            b=b/2;//把b变成原来的一半继续乘
        }
        return res;
    }

还有一种非递归写法，运用到了位运算，可以理解为把指数b转化为二进制数，然后因为二进制转十进制就是对应各个位上2的几次方相加，同时因为**xm+n=xm\*xn**，所以这样就可以转化为各个位上的指数拆开后，再把结果相乘即可

这样484有点不太好懂？我来举个栗子吧，比如说我们现在要求的是317

把17转为二进制就是**(17)10=(10001)2**

我们代入代码手动模拟一下

int ksm(int a,int b,int n){
        int res=1;//记录答案
        while(b){
            if(b&1) res=res*a%n;
    //位运算，如果当前这一位上b是1就要乘上这一位指数算出的幂
            a=a*a%n;//累乘a
            b=b>>1;//位运算，相当于b/2
        }
        return res;
    }

首先a=3，b=17，n就先不管

接下来进入循环，因为b的最后一位为1，符合条件，所以答案res要乘上3，于是现在res=3，然后a=9，b=(1000)2

继续循环，此时b的最后一位是0，所以不符合条件，于是res没有变化，a=81，b=(100)2

这样继续下去如果记录过程的话，最后答案**res=3(1×2^0)×3(0×2^1)×3(0×2^2)×3(0×2^3)×3(1×2^4)=31×90×810×65610×430467211**

就是酱紫！嚯呀QWQ

**go back**

--------------------

> **二.矩阵快速幂**

矩阵快速幂的话主要是对于方阵乘幂来讲的啦

方阵乘幂是虾米嘞？

就是将一个方阵n次方，注意是方阵！方阵！行列数相等的那种！不是方阵是不能进行乘幂运算的！QAQ

由于矩阵乘法满足结合律，所以可以用快速幂来求方阵乘幂