【模板】快速幂

题意

计算 $a^b\bmod p$ ，并按指定格式输出。

思路

快速幂把指数写成二进制，只使用 $O(\log b)$ 次平方和乘法。Python 已经在内置函数中实现了这一算法：

python

1pow(a, b, modulus)

三参数版本会在运算过程中持续取模，不会先构造可能极大的 a ** b。OJ 中应优先使用它，而不是写成 a ** b % modulus。

Python 知识

pow(base, exponent, modulus) 是模快速幂，复杂度为 $O(\log exponent)$ 。
f-string 可以直接拼出题目要求的固定格式。
Python 内置 pow 由底层高效实现，模板题没有必要手写循环来代替它。

代码

python

1
2a, b, modulus = map(int, input().split())
print(f"{a}^{b} mod {modulus}={pow(a, b, modulus)}")

原有手写 C++ 快速幂仍可用于理解二进制拆分：

cpp

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#include <bits/stdc++.h>
using namespace std;

long long a, b, p;

long long fast_power(long long base, long long exp, long long mod) {
    long long ans = 1 % mod;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) {
            ans = ans * base % mod;
        }
        base = base * base % mod;
        exp >>= 1;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> a >> b >> p;
    cout << a << "^" << b << " mod " << p << "=" << fast_power(a, b, p) << '\n';
    return 0;
}

复杂度

时间 $O(\log b)$ ，除大整数运算内部空间外只使用 $O(1)$ 个变量。

总结

这题最能体现 Python 相对 C++ 的语言特性：三参数 pow 就是可直接提交的标准模快速幂。

目录

题意

思路

Python 知识

代码

复杂度

总结