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

题目链接

题目描述

给定 $T$ 组数据，每组数据包含三个正整数 $a, b, m$ 。求 $a^b \pmod m$ 的值。

输入描述: 第一行一个整数 $T$ ，表示数据组数。接下来 $T$ 行，每行三个正整数 $a, b, m$ 。

输出描述: 对于每组数据，输出一行，表示 $a^b \pmod m$ 的结果。

解题思路

本题要求计算 $a^b \pmod m$ 。当指数 $b$ 非常大时，直接使用循环乘以 $b$ 次的方法（时间复杂度为 $\mathcal{O}(b)$ ）会超时。因此，我们需要使用 快速幂算法，也叫作 二进制取幂 (Binary Exponentiation)，将时间复杂度优化到 $\mathcal{O}(\log b)$ 。

快速幂原理

该算法的核心思想是利用指数 $b$ 的二进制表示。任何一个正整数 $b$ 都可以被表示为其二进制形式，例如： $b = c_k \cdot 2^k + c_{k-1} \cdot 2^{k-1} + \dots + c_1 \cdot 2^1 + c_0 \cdot 2^0$ 其中 $c_i \in \{0, 1\}$ 是 $b$ 的二进制位。

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

观察这个式子，每一项都是 $a^{(2^i)}$ 的形式。我们可以很方便地通过自乘来递推得到这些项： $a^1, a^2, a^4, a^8, \dots$ 。 $a^2 = (a^1)^2$ $a^4 = (a^2)^2$ $a^8 = (a^4)^2$ ... $a^{2^i} = (a^{2^{i-1}})^2$

因此，我们只需要遍历 $b$ 的二进制位。如果第 $i$ 位是 1（即 $c_i = 1$ ），我们就将最终结果乘上 $a^{2^i}$ 。

算法步骤 (迭代实现):

初始化结果 res = 1 % m。将结果初始化为 1 % m 而不是简单的 1 是一个关键细节。它能正确处理模数为 1 的边界情况：当 m=1，1 % 1 为 0，符合任何数模 1 都为 0 的规则；当 m>1，1 % m 依然为 1，不影响常规计算。
将底数 $a$ 对 $m$ 取模，即 a = a % m。这可以防止中间计算溢出，并利用模运算性质 $(x \cdot y) \pmod m = ((x \pmod m) \cdot (y \pmod m)) \pmod m$ 。
当 $b > 0$ 时，进入循环： a. 判断 $b$ 的最低位：如果 $b$ 是奇数 (即 b & 1 == 1)，说明 $b$ 的二进制表示中当前最低位为 1，此时需要将 res 乘上当前的 a。即 res = (res * a) % m。 b. 更新底数：将 a 平方，即 a = (a * a) % m。这对应于从 $a^{2^i}$ 计算 $a^{2^{i+1}}$ 。 c. 更新指数：将 $b$ 右移一位（即 b >>= 1 或 b = b / 2），以检查下一位。
循环结束后，res 就是 $a^b \pmod m$ 的结果。

代码

cpp
java
python

#include <iostream>

using namespace std;

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin >> T;
    while (T--) {
        long long a, b, m;
        cin >> a >> b >> m;
        cout << power(a, b, m) << endl;
    }
    return 0;
}

import java.util.Scanner;

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

    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(power(a, b, m));
        }
    }
}

# Python 的内置函数 pow(base, exp, mod) 是执行模幂运算最地道、
# 最高效的方式。它能正确处理 m=1 的边界情况，返回 0。

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

算法及复杂度

算法：快速幂 / 二进制取幂
时间复杂度： $\mathcal{O}(T \cdot \log b)$ ，对于每个测试用例，快速幂算法需要对指数 $b$ 进行对数次操作。
空间复杂度： $\mathcal{O}(1)$ ，迭代实现只需要常数空间。