快速幂

快速幂

适用场景

快速求出 $a^k \bmod p$ 的值。

算法原理 & 步骤分析

快速幂原理是基于二进制枚举的思想。

对于整数 $a$ 的任意幂数 $k$，$k$ 都可以用二进制进行拆分，并且只会由 $\left [2^0, 2^{\lfloor \log k \rfloor} \right]$ 中的部分数组合而成。

例如 $k_1 = 4 = (100)_2, k_2 = 7 = (111)_2$，均为三位二进制数，只由 $2^0、2^1、2^2$ 中的部分数构成。这样原式就可转化为：

因此，对于给定的幂数 $k$，我们可以先预处理出 $\left[ a^{2^{0}},\ a^{2^{\lfloor \log k \rfloor}} \right]$ 中的所有数。时间复杂度为 $O(\log k)$

然后依次枚举 $k$ 的二进制表示的每一位，每次枚举时 $a$ 都需要自我累乘一次：

a = (LL)a * a % p；如果该位为 $1$，就将当前累乘的 $a$ 计入答案：res = (LL)res * a % p，如果该位为 $0$，就不予计入，枚举下一位。

注：这里 $a, k, p$ 满足 $1\leq a, k, p\leq 2\times 10^9$，所以在自我累乘和答案计入时可能会溢出整数范围，需要开 long long。

枚举完 $k$ 的二进制表示数的所有位后，累乘的 res 就是答案。

完整代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

typedef long long LL;

int quick_mi(int a, int k, int p)
{
    int res = 1;

    while (k)
    {
        if (k & 1) res = (LL)res * a % p;
        k >>= 1;
        a = (LL)a * a % p;
    }
    return res;
}

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int a, k, p;
        scanf("%d%d%d", &a, &k, &p);
        printf("%d\n", quick_mi(a, k, p));
    }
    return 0;
}