AcWing 875. 快速幂

◎

本节目标

按指数二进制位迭代计算模幂。

题意与约束

对多组 a b p 输出 a^b mod p。指数可以很大，p≤2×10^9，答案始终规范到 0..p-1。

第一反应与瓶颈

连续相乘 b 次直观但要 O(b) 轮；当 b 很大时，真正需要利用的是它的二进制表示。

数学关系与算法推导

若 b 的当前最低位为 1，就把当前 base 乘入 result；无论最低位为何，下一位对应的底数都是 base²。每轮右移 b，因此仅处理 O(log b) 位。

正确性依据

循环开始时，result × base^exponent 与原始幂在模 p 下同余。读掉一位 1 后把该位贡献乘入 result；平方和右移把剩余指数转换为下一轮表示，不变量保持到指数为零。

样例执行过程

3^2 mod 5：最低位 0，底数变为 9 mod 5 = 4；下一位为 1，答案得到 4。指数为零时停止。

代码实现

C++

C++17

#include <iostream>
using namespace std;

long long modPow(long long base, long long exponent, long long modulus) {
    base %= modulus;
    long long result = 1 % modulus;
    while (exponent > 0) {
        if ((exponent & 1) != 0) {
            result = result * base % modulus;
        }
        base = base * base % modulus;
        exponent >>= 1;
    }
    return result;
}

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

    int count;
    cin >> count;
    while (count-- > 0) {
        long long base, exponent, modulus;
        cin >> base >> exponent >> modulus;
        cout << modPow(base, exponent, modulus) << '\n';
    }
    return 0;
}
#endif

Python

Python 3

import sys


def mod_pow(base: int, exponent: int, modulus: int) -> int:
    base %= modulus
    result = 1 % modulus
    while exponent > 0:
        if exponent & 1:
            result = result * base % modulus
        base = base * base % modulus
        exponent >>= 1
    return result


def main() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    count = data[0]
    answers = [str(mod_pow(*data[index:index + 3])) for index in range(1, 1 + 3 * count, 3)]
    print('\n'.join(answers))


if __name__ == '__main__':
    main()

复杂度分析

时间 O(log b)，空间 O(1)。

边界与易错点

b = 0 时结果为 1 mod p。每次相乘后立刻取模；由于两个因子都小于 p≤2×10^9，乘积小于 4×10^18，标准 C++17 的 long long 足够。若模数上界更大，必须改用可移植模乘，不能让 64 位中间值溢出。

模式迁移

凡是“指数大但乘法可结合”的问题都可按位拆分；后续快速幂求逆元用同一工具计算 x^(p-2)。回到欧拉函数与模运算。