题解 | #【模板】快速幂Ⅰ ‖ 整数#

题目链接

【模板】快速幂Ⅰ ‖ 整数

题目描述

对于给定的三个正整数 $a, b, m$ ，计算 $a^b \pmod m$ 。

解题思路

本题要求计算 $a$ 的 $b$ 次方对 $m$ 取模的结果。这是一个经典的数论问题，通常使用快速幂（Fast Power）算法来高效解决。

朴素算法及其缺陷

最直观的方法是使用一个循环，将 $a$ 连乘 $b$ 次，并在每一步都对 $m$ 取模。这种方法的时间复杂度是 $\mathcal{O}(b)$ 。当 $b$ 的值非常大时（例如 $b \ge 10^9$ ），这个算法会因为超时而无法通过。
快速幂算法（二进制取幂）

快速幂算法的核心思想是利用指数 $b$ 的二进制表示来减少乘法次数，将时间复杂度从 $\mathcal{O}(b)$ 优化到 $\mathcal{O}(\log b)$ 。

其原理如下：任何一个整数 $b$ 都可以表示为其二进制形式： $b = c_k 2^k + c_{k-1} 2^{k-1} + \dots + c_1 2^1 + c_0 2^0$ ，其中 $c_i \in \{0, 1\}$ 。

因此， $a^b$ 可以写成： $a^b = a^{c_k 2^k + \dots + c_0 2^0} = a^{c_k 2^k} \cdot a^{c_{k-1} 2^{k-1}} \cdot \dots \cdot a^{c_0 2^0}$

我们可以观察到，式中的每一项 $a^{2^i}$ 都可以通过前一项 $a^{2^{i-1}}$ 平方得到，即 $a^{2^i} = (a^{2^{i-1}})^2$ 。这启发我们可以在迭代中同时计算 $a, a^2, a^4, a^8, \dots$ 。

迭代实现步骤：
- 初始化结果 result = 1。
- 初始化底数 base = a。
- 循环，当 $b > 0$ 时：
  - 检查 $b$ 的二进制最低位是否为 $1$ (即 b % 2 == 1)。如果是，说明 $a^b$ 的展开式中包含当前的 base 项（ $a^{2^i}$ ），我们就将 result 乘以 base。
  - 为了准备下一轮迭代，我们将 base 平方，即 base = base * base，使其变为 $a^{2^{i+1}}$ 。
  - 将 $b$ 右移一位（即 b = b / 2），以检查 $b$ 的下一个二进制位。
- 在所有乘法运算后都必须对 $m$ 取模，以防止中间结果溢出。
- 特殊情况：当 $m=1$ 时，任何数对 $1$ 取模的结果都是 $0$ ，可以直接返回。

代码

c++
java
python

#include <iostream>

using namespace std;

long long fast_power(long long base, long long power, long long mod) {
    if (mod == 1) {
        return 0;
    }
    long long result = 1;
    base %= mod;
    while (power > 0) {
        if (power % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        power /= 2;
    }
    return result;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        long long a, b, m;
        cin >> a >> b >> m;
        cout << fast_power(a, b, m) << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static long fastPower(long base, long power, long mod) {
        if (mod == 1) {
            return 0;
        }
        long result = 1;
        base %= mod;
        while (power > 0) {
            if (power % 2 == 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            power /= 2;
        }
        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            long a = sc.nextLong();
            long b = sc.nextLong();
            long m = sc.nextLong();
            System.out.println(fastPower(a, b, m));
        }
    }
}

def fast_power(base, power, mod):
    if mod == 1:
        return 0
    result = 1
    base %= mod
    while power > 0:
        if power % 2 == 1:
            result = (result * base) % mod
        base = (base * base) % mod
        power //= 2
    return result

def main():
    T = int(input())
    for _ in range(T):
        a, b, m = map(int, input().split())
        print(fast_power(a, b, m))

if __name__ == "__main__":
    main()

算法及复杂度

算法：数论、快速幂（二进制取幂）
时间复杂度： $\mathcal{O}(\log b)$ 。循环的次数取决于指数 $b$ 的二进制位数，即 $\lfloor \log_2 b \rfloor + 1$ 。
空间复杂度： $\mathcal{O}(1)$ 。算法只使用了常数个变量来存储中间结果。