快速幂

一、算法思想

快速幂，思想是将取幂的任务 按照指数的二进制表示来分割成更小的任务。

首先我们将 $n$ 表示为 2 进制，举一个例子：

$3^{13} = 3^{(1101)_2} = 3^8 \cdot 3^4 \cdot 3^1$

因为 $n$ 有 $\lfloor \log_2 n \rfloor + 1$ 个二进制位，因此当我们知道了 $x^1, x^2, x^4, x^8, \dots, x^{2^{\lfloor \log_2 n \rfloor}}$ 后，我们只用计算 $\Theta(\log n)$ 次乘法就可以计算出 $x^n$。

根据以上推导，可把计算 $x^n$ 转化为解决以下两个问题：

• 计算 $x^1, x^2, x^4, x^8, \dots, x^{2^{\lfloor \log_2 n \rfloor}}$ 的值： 循环赋值操作 $x = x^2$ 即可；
• 取出指数 n 的二进制中的每一位：当值为 1 时，结果累乘 x。

二、算法模板

C++

typedef long long LL;

LL binPow(LL x, LL k)
{
    LL ans = 1;
    while (k) {
        if (k & 1) ans *= x;
        x *= x;
        k >>= 1;
    }
    return ans;
}

typedef long long LL;

LL binPow(LL x, LL k, LL p)
{
    LL ans = 1;
    while (k) {
        if (k & 1) ans = ans * x % p;
        x = x * x % p;
        k >>= 1;
    }
    return ans;
}

说明

模意义下取幂：取模的运算不会干涉乘法运算，因此我们只需要在计算的过程中取模即可。

三、代码实战

AcWing 0875

---

题目：快速幂

给定 $n$ 组 $a_i,b_i,p_i$，对于每组数据，求出 $a_{i}^{b_{i}} \bmod p_{i}$ 的值。

输入格式

第一行包含整数 $n$。

接下来 $n$ 行，每行包含三个整数 $a_i,b_i,p_i$。

输出格式

对于每组数据，输出一个结果，表示 $a_{i}^{b_{i}} \bmod p_{i}$ 的值。

每个结果占一行。

数据范围

$1 \le n \le 100000$

$1 \le a_i,b_i,p_i \le 2 \times 10^9$

输入样例：

2

3 2 5

4 3 9

输出样例：

4

1

解答代码：

#include <iostream>

using namespace std;

typedef long long LL;

LL binPow(LL x, LL k, LL p)
{
    LL ans = 1;
    while (k) {
        if (k & 1) ans = ans * x % p;
        x = x * x % p;
        k >>= 1;
    }
    return ans;
}

int main()
{
    int n;
    scanf("%d", &n);
    
    while (n--) {
        LL x, k, p;
        scanf("%lld%lld%lld", &x, &k, &p);
        printf("%lld\n", binPow(x, k, p));
    }
    
    return 0;
}