快速幂

2024-01-16 15:11:46

1、快速幂是用来做什么的？

（1）快速求出 $a^k$ 的结果！比如 $2^{100}$ 的结果。简单粗暴快速幂

（2）快速求出 $a^k$ $mod$ $p$ 的结果！比如 $2^{100} \% 7$ 的结果。 常见快速幂

2、快速幂算法的原理

通过将指数拆分成几个因数相乘的形式，来简化幂运算。在我们计算$3^{13}$ 的时候，普通的幂运算算法需要计算$13$次，但是如果我们将它拆分成$3^{8+4+1}$ ，再进一步拆分成只需要计算$4$次。嗯？哪来的$4$次？，别急，接着看。

这种拆分思想其实就是借鉴了二进制与十进制转换的算法思想，我们知道$13$的二进制是$1101$，可以知道：
$13=1\times2^{3} + 1\times2^{2} + 0\times2^{1} + 1\times2^{0} = 8 + 4 + 1$

原理就是利用位运算里的位移“>>”和按位与“&”运算，代码中 $k \& 1$其实就是取$k$的二进制最低位，用来判断最低位是$0$还是$1$，再根据是$0$还是$1$决定乘不乘，不理解的话联系一下二进制转换的过程。$k >>= 1$其实就是将$k$的二进制向右移动一位，就这样位移、取最低位、位移、取最低位，这样循环计算，直到指数$k$为$0$为止，整个过程和我们手动将二进制转换成十进制是非常相似的。

普通幂算法是需要循环指数次，也就是指数是多少就要循环计算多少次，而快速幂因为利用了位移运算，只需要算“指数二进制位的位数”次，对于$13$来说，二进制是$1101$，有$4$位，就只需要计算$4$次，快速幂算法时间复杂度是$O(logn)$级别，对于普通幂需要计算一百万次的来说，快速幂只需要计算$6$次，这是速度上质的飞跃，但是需要多注意溢出的问题。

3、举个栗子

把$3^{13}$进行转化：
$3^{13}=3^{8+4+1}=3^{8}\times3^{4}\times3^{1}$
如果我们能求出$3^{1}$,$3^{4}$,$3^{8}$，我们就可以求出最后的$3^{13}$，因为把它们乘在一起就可以了嘛。那怎么求呢？

$3^{1}$可以求，因为就是3嘛，其它的呢？其它的有哪些需要我们提前准备好呢？
有： $3^{1}$，$3^{2}$，$3^{4}$，$3^{8}$ ，注意，只有这几个啊，其它的$3^{3}$，$3^{5}$，$3^{6}$，$3^{7}$可没有啊，不需要啊，因为有上面的这几个，就可以完美的组装出13了！

这些东东怎么求啊？这就简单了，就是每次翻一倍就是下一个了，比如 $3^{4}$ = $3^{2} \times 3^{2} $

先来一个原始版本的快速幂，不考虑什么溢出之类，简单粗暴的来一拔：

4、简单粗暴快速幂（原始版本）

此方法是我用来方便理解的，不可用于实际工作中，或者说，没有实用价值。因为一来系统中有现成的$pow(n,m)$,另一个是不防溢出基本在数论题中无用。

#include <iostream>
using namespace std;

typedef long long LL; //十年OI一场空，不开LONG LONG见祖宗

int qmi(int a, int k) {
    int res = 1; 
    while (k) {                    
        if (k & 1) res = res * a;  
        k >>= 1;                   
        a = (LL) a * a;                 
    }
    return res;
}


int main() {
    cout<<qmi(3,4)<<endl;
    return 0;
}

5、简单粗暴快速幂+高精度乘法版本

这个就有点纠结了，因为什么呢？一般我们使用高精度，都是高精度乘以低精度，通常这样就够用了。但在这里不行，为啥呢？因为这里面是需要记录两个东西：
(1)结果res。
(2)上一轮的结果a，本轮把它平方做为本轮的底。

这两个家伙可都不是善茬，都可能是非常大的数字，都可能爆$long\ long$,所以，都需要把它们两个放入高精度中，看来高精度乘法的两个模板（高精乘低精，高精乘高精）都是有必要背诵的。

下面是高精度乘以高精度的模板

#include <bits/stdc++.h>

using namespace std;

/**
 * 功能：高精度乘高精度模板
 * @param A
 * @param b
 * @return
 */
vector<int> mul(vector<int> &A, vector<int> &B) {
    //初始化大小
    vector<int> C(A.size() + B.size());
    //先放里再说
    for (int i = 0; i < A.size(); i++)
        for (int j = 0; j < B.size(); j++)
            C[i + j] += A[i] * B[j];

    //处理余数
    for (int i = 0, t = 0; i < C.size(); i++) {
        t += C[i];
        if (i >= C.size()) C.push_back(t % 10);
        else C[i] = t % 10;
        t /= 10;
    }
    //去掉前导0
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

int main() {
    string a, b;
    cin >> a >> b;
    //准备动作
    vector<int> A, B;
    for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');
    //计算
    vector<int> C = mul(A, B);
    //倒序输出
    for (int i = C.size() - 1; i >= 0; i--) cout << C[i];
    return 0;
}

下面是高精度+快速幂的模板

//快速幂+高精度 a^b
vector<int> qmi(int a, int b) {
    vector<int> ans; //结果数组
    ans.push_back(1); //底

    vector<int> A;  //上一个依赖项
    A.push_back(a);

    while (b) {
        if (b & 1) ans = mul(ans, A);
        b >>= 1;
        A = mul(A, A);
    }
    return ans;
}

这里需要特别指出一个练习题：https://www.luogu.com.cn/problem/P1045，洛谷的高精度+快速幂的练习题，还需要对高精度模板再进化，时刻保持$500$位！

时刻保留500位的代码如下：


//高精度乘法模板(高精乘高精)
vector<int> mul(vector<int> &A, vector<int> &B) {
    //只保留500个长度
    if(A.size()>500) A.resize(500);
    if(B.size()>500) B.resize(500);

    int la = A.size(), lb = B.size();
    vector<int> C(la + lb + 10, 0);//提前申请结果所需的空间
    for (int i = 0; i < la; i++)
        for (int j = 0; j < lb; j++)
            C[i + j] += A[i] * B[j];

    for (int i = 0; i < C.size(); i++)
        if (C[i] >= 10) {
            C[i + 1] += C[i] / 10;
            C[i] %= 10;
        }
    //处理前导0
    while (C.size() > 1 && C.back() == 0)C.pop_back();

    //只保留500个长度
    if(C.size()>500) C.resize(500);
    return C;
}

6、不断模防止溢出的快速幂

#include <iostream>
using namespace std;

//防止和爆INT
typedef long long LL;

int n;

// 快速幂 (a^k)%p
int qmi(int a, int k, int p) {
    int res = 1; //答案
    while (k) {                             //一路让k变小直到为0停止
        if (k & 1) res = (LL) res * a % p;  //如果k的个位是1的话
        
        k >>= 1;                            //右移一位
        a = (LL) a * a % p;                 //1-2-4-8-16，就是每进一位，是把a=a*a
    }
    return res;
}

//快速幂
int main() {
    scanf("%d", &n);
    while (n--) {
        int a, k, p;
        scanf("%d%d%d", &a, &k, &p);
        printf("%d\n", qmi(a, k, p));
    }
    return 0;
}

码农公寓