什么是快速幂？

快速幂（Exponentiation by squaring）是一种高效计算大数幂运算的算法，时间复杂度为O(log n)，比朴素的O(n)方法快得多。

板子

1
2
3
4
5
6
7
8
9
10
long long qpow(long long a, long long b, long long m) { // return (a ^ b) mod m
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res % m;
}

快速幂的二进制优化原理

传统计算方式

对于 $3^{13}$ 的朴素计算需要13次乘法：
$$3^{13} = 3 \times 3 \times \cdots \times 3 \quad (共13次)$$

二进制优化思路

将指数13分解为二进制 $1101_2$：
$$13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0$$

对应幂运算分解：
$$3^{13} = 3^{8} \times 3^{4} \times 3^{1}$$

计算过程演示

位权 二进制位 当前底数 当前位值 是否需要相乘
$2^0$ (1) 1 $3^1$ 3 ✓ (res × 3)
$2^1$ (2) 0 $3^2$ 9 ✗
$2^2$ (4) 1 $3^4$ 81 ✓ (res × 81)
$2^3$ (8) 1 $3^8$ 6561 ✓ (res × 6561)

计算步骤：

  1. 初始化 $res = 1$
  2. 检查最低位1：$res = 1 \times 3 = 3$
  3. 底数平方：$3 \rightarrow 3^2 = 9$
  4. 检查第二位0：不操作
  5. 底数平方：$9 \rightarrow 9^2 = 81$
  6. 检查第三位1：$res = 3 \times 81 = 243$
  7. 底数平方：$81 \rightarrow 81^2 = 6561$
  8. 检查第四位1：$res = 243 \times 6561 = 1594323$

数学形式化表达

对于 $a^b$，设 $b$ 的二进制表示为 $(b_k b_{k-1} \ldots b_0)_2$：
$$
a^b = \prod_{i=0}^{k} (a^{2^i})^{b_i} \quad \text{其中} \ b_i \in {0,1}
$$

复杂度对比

方法 乘法次数 时间复杂度
朴素算法 $O(n)$ 13次
快速幂 $O(\log n)$ 4次（log₂13≈3.7）

Q1 P1226 【模板】快速幂 - 洛谷

题目描述

给你三个整数 $a,b,p$，求 $a^b \bmod p$。

输入格式

输入只有一行三个整数，分别代表 $a,b,p$。

输出格式

输出一行一个字符串 a^b mod p=s，其中 $a,b,p$ 分别为题目给定的值， $s$ 为运算结果。

输入输出样例 #1

输入 #1

1
2 10 9

输出 #1

1
2^10 mod 9=7

说明/提示

样例解释

$2^{10} = 1024$，$1024 \bmod 9 = 7$。

数据规模与约定

对于 $100%$ 的数据，保证 $0\le a,b < 2^{31}$，$a+b>0$，$2 \leq p \lt 2^{31}$。

思路

请先自己思考一下喵

其实就是直接照搬板子就好啦
但是要稍微注意一下输出格式

代码

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include "bits/stdc++.h"
/*
关注b站<Feijoa_Li>谢谢喵
UID:248614274
https://space.bilibili.com/248614274
 */
using namespace std;

using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
using i128 = __int128;

#define int long long
#define Ist first
#define Ind second
#define itn long long
#define O (int)0
#define endl "\n"
#define PII pair<int, int>
const int inf = 1e18;

int qpow(int a, int b, int m) {
    a %= m;
    int res = 1;
    while (b > 0) {
        if (b & 1) res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res % m;
}
/*

*/
void slu() {
    int a, b, p;
    cin >> a >> b >> p;
    // a^b mod p=res
    cout << a << '^' << b << " mod " << p << '=' << qpow(a, b, p) << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    // cin >> t;

    while (t--) slu();
    return 0;
}