# 快速幂


<!--more-->

# 快速幂

### 适用场景

快速求出 $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$ 中的部分数构成。这样原式就可转化为：

$$a^{k_1} = a^{4} = a^{0\times 2^{0} + 0\times 2^{1} + 1\times 2^{2}}$$

$$a^{k_2} = a^{7} = a^{1\times 2^{0} + 1\times 2^{1} + 1\times 2^{2}} = a^{2^{0}}\cdot a^{2^{1}}\cdot a^{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` 就是答案。


#### 完整代码

```cpp
#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;
}
```


---

> 作者: yitao  
> URL: https://yitaonote.com/2025/302d3a9/