CC++ & Algorithm

快速幂取模运算

极难2
语言版本：通用
概述：让你学会在计算大数幂的同时取模，避免结果溢出，常用于密码学和数论。

快速幂取模：算大幂时不让数字“爆表”

在编程中，我们经常需要计算一个很大的数的幂，比如 7^1000。这个数会超级大，连计算机都存不下（除非你用 Python 大整数，但速度会变慢）。更常见的情况是：我们只需要结果模某个数，比如 (7^1000) % 1000000007。这时候就可以用“快速幂取模”算法，既快又不会溢出。简单说，这个算法就是“一边算大幂，一边取余数”，让每一步的中间结果都乖乖待在安全范围内。

为什么需要取模？—— 想象分糖果的场景

假设你有7块糖，要平均分给1000个小朋友，每次分一个小朋友，一共需要分1000次。但你觉得太麻烦，于是想到一个办法：每次数出7块糖，看能不能正好让1000个小朋友每人得到一块？其实你不需要真的把糖数到 7×1000 块那么多，只需要每次关心“当前糖数除以1000的余数”就行了。比如一开始有7块，7÷1000 余7；然后你又拿来7块，总共14块，14÷1000 余14……每次都是加7块，然后取余数，最后得到的就是余数。快速幂取模也是类似的：我们只关心每一步乘法之后的结果对模数取余，因为乘法和取模可以交换顺序——这就是神奇的运算性质：

(a × b) % m = ( (a % m) × (b % m) ) % m

有了这个性质，我们就可以在快速幂的每一步都及时取模，数字永远不超过 m 的大小，既安全又快速。

数学原理：一边平方一边取模

快速幂的核心思想是把指数 n 拆成二进制位，比如 n=1000 的二进制是 1111101000。我们通过不断将底数平方来得到不同次幂，然后在需要的时候乘到结果里。取模只是让每一步的乘法结果都做一次 % m。
公式推导：设 res 和 base 都是小于 m 的数，那么 (res × base) % m 就等于先乘再取模，因为我们已经在每一步都取了模，所以 res 和 base 始终小于 m，不会溢出。

算法步骤详解（以 7^1000 mod 1000000007 为例）

  1. 初始化

    • res = 1 % m （如果 m=1，任何数模1都得0，所以 res初始化为0；通常 m>1，1%m=1）
    • base = a % m = 7 % 1000000007 = 7
    • n = 1000

  2. 循环（每次处理 n 的一个二进制位）

    • 检查 n 的最低位（n & 1）：如果是1，说明当前 base 的幂需要乘到结果里，执行 res = (res * base) % m
    • 然后 base 平方：base = (base * base) % m
    • 最后 n 右移一位：n >>= 1（相当于 n 除以2，去掉最低位）
    • 重复直到 n 变为0

  3. 返回结果 res

举个例子简化：计算 3^5 mod 5（5的二进制是101，即 3^4 × 3^1）

  • 初始：res=1, base=3, n=5
  • 第一步：n&1=1 → res=13%5=3, base=33%5=4, n>>=1 → n=2
  • 第二步：n&1=0 → 不乘, base=4*4%5=1, n>>=1 → n=1
  • 第三步：n&1=1 → res=31%5=3, base=11%5=1, n>>=1 → n=0
  • 结果 res=3，即 3^5=243，243%5=3，正确。

新手常犯的错误

  1. 忽略模数为1的情况
    如果 m=1，任何数模1都等于0。但代码里如果直接写 res = 1 % m 会得到0，而 while 循环里如果 base 也取模为0，乘法结果永远为0，没问题。但有些人会写成 res = 1，对于 m=1 就会返回1（错误）。所以一定要写成 res = 1 % m 来处理边界。

  2. 指数为0的情况
    a^0 = 1（规定），如果 n=0，循环不执行，直接返回 res=1%m，正确。但注意 a^0 mod m = 1 mod m，如果 m=1，返回0也是对的。

  3. 中间乘法溢出（C++ 尤其注意）
    即使我们每一步都取模，但两个小于 m 的数相乘，结果可能超过 int 或 long long 的范围。例如 m 接近 10^18，两个数相乘会达到 10^36，远超 64 位整数范围。解决方式：

    • 使用 __int128（很多编译器支持，如 GCC、Clang）
    • 使用快速乘（类似快速幂的思路，把乘法拆成加法和取模）
    • Python 用户不用担心，因为 Python 整数无限大，但为了性能，依然建议取模。

  4. 忘记对 a 先取模
    如果 a 很大（比如 a = 10^18），直接传入函数，base = a % mod 这一步能把它缩小，否则后续 base 平方会更大。所以一定要先 base = a % mod。

完整可运行代码示例

C++ 版本（带详细注释，使用 __int128 防止溢出）

#include <iostream>
using namespace std;

// 快速幂取模：计算 (a^n) % mod
// 使用 __int128 确保乘法不溢出（需要编译器支持）
// 参数范围：0 <= a, n, mod <= 1e18（mod>0）
long long modPow(long long a, long long n, long long mod) {
    long long res = 1 % mod;          // 初始化结果，处理 mod=1
    long long base = a % mod;         // 先对底数取模，避免 base 太大
    while (n > 0) {
        if (n & 1LL) {                // 如果当前二进制位为1
            res = (long long)((__int128)res * base % mod); // 使用 __int128 防溢出
        }
        base = (long long)((__int128)base * base % mod);   // base 平方并取模
        n >>= 1;                      // 指数右移一位（相当于除以2）
    }
    return res;
}

int main() {
    // 测试几个例子
    long long a1 = 7, n1 = 1000, mod1 = 1000000007;
    cout << a1 << "^" << n1 << " mod " << mod1 << " = " << modPow(a1, n1, mod1) << endl;

    long long a2 = 3, n2 = 5, mod2 = 5;
    cout << a2 << "^" << n2 << " mod " << mod2 << " = " << modPow(a2, n2, mod2) << endl; // 应输出3

    long long a3 = 123, n3 = 456, mod3 = 10007;
    cout << a3 << "^" << n3 << " mod " << mod3 << " = " << modPow(a3, n3, mod3) << endl; // 练习结果

    return 0;
}

Python 版本（简洁优雅，无需担心溢出）

def mod_pow(a: int, n: int, mod: int) -> int:
    """
    计算 (a^n) % mod
    :param a: 底数（非负整数）
    :param n: 指数（非负整数）
    :param mod: 模数（正整数）
    :return: 整数结果
    """
    res = 1 % mod          # 初始化结果，如果 mod==1 则 res=0
    base = a % mod         # 底数先取模
    while n > 0:
        if n & 1:          # 检查最低位是否为1
            res = (res * base) % mod
        base = (base * base) % mod
        n >>= 1            # 右移一位，相当于 n //= 2
    return res

# 测试
if __name__ == "__main__":
    print(mod_pow(7, 1000, 1000000007))
    print(mod_pow(3, 5, 5))           # 应输出3
    print(mod_pow(123, 456, 10007))   # 练习结果

为什么取模后还能用快速幂？

因为取模运算对乘法有分配律： (a × b) % m = [(a%m) × (b%m)] % m。所以我们在每一步都把中间结果变小，不影响最终取模的结果。这样即便 a^n 巨大无比，我们也能算出来。这个性质适用于加法和减法，但注意乘方没有类似的分配律（比如 (a^n) % m 不能写成 (a%m)^(n%m) % m，那样会出错），所以必须用快速幂逐次计算。

生活中的更多类比

  • 零花钱：你每天得到5元零花钱，想知道100天后你总共有多少元（不考虑花掉），但你只关心总钱数模100（比如你要存到整数百元才存入银行）。快速幂取模就像每次加5元后立刻减去100的倍数，只记录余数，最后一看就知道还差多少到100。
  • 考试排名：你每次考试进步2名，想知道考试了10次后你的排名模5（比如座位号循环）。如果直接算2^10=1024次进步，太夸张了，但用快速幂取模，每次进步后只保留余数，很快就能得到结果。

常见应用

  • 密码学：RSA 算法中需要计算大数的模幂，比如 c = m^e mod n，这是加密的核心。
  • 组合数学：计算组合数 C(n, k) 时，需要用到阶乘和逆元，逆元常用快速幂取模（费马小定理）计算，比如 a^(p-2) mod p，p是质数。
  • 矩阵快速幂：求斐波那契数列第 n 项时，结果可能非常大，需要用矩阵乘法加取模，最后输出模某个数。
  • 哈希算法：某些哈希函数需要对大数取模。

练习

  1. 计算 (123^456) % 10007，用上面代码验证结果。
  2. 如果 mod 是质数，可以用快速幂求逆元（费马小定理）。已知 7 是质数，求 3 在模 7 下的逆元（即找一个数 x，使得 3*x ≡ 1 mod 7）。提示：x = 3^(7-2) mod 7。

相关知识点指引

学完快速幂取模，你还可以继续探索：

  • 普通快速幂：不取模时计算大整数幂（但注意范围）。
  • 矩阵快速幂：把底数换成矩阵，可以高效计算斐波那契数列、线性递推等。
  • 费马小定理：用于质数模数下的逆元计算，与快速幂取模紧密结合。
  • 欧拉定理：推广到非质数模数，用于更一般的逆元计算。
  • 快速乘：解决两数相乘会溢出的问题（用类似快速幂的二分思路）。

总结

快速幂取模就是把快速幂和模运算结合，既快又防溢出。写法跟普通快速幂几乎一样，只是每步乘法后加了 % mod。记住：取模不会破坏幂运算的结果，但它能让我们在整数范围内安全计算。下次遇到“大数的幂取模”问题，你就能轻松对付了！

例题精讲

1单选题

快速幂取模算法计算a^b mod m时，时间复杂度是多少？

AO(b)
BO(log b)
CO(a)
DO(1)
2判断题

在快速幂取模算法中，当指数b为偶数时，可以将a^b mod m转化为(a^(b/2) mod m)^2 mod m。

3填空题
下面是一个快速幂取模函数，请补充缺失的一行。
int fastPowMod(int a, int b, int m) {
    int res = 1;
    a %= m;
    while (b > 0) {
        if (b & 1) {
            res = (res * a) % m;
        }
        a = (a * a) % m;
        ___;
    }
    return res;
}
4单选题

使用快速幂取模计算3^11 mod 5，算法过程中res变量的初始值为1，第一次遇到指数最低位为1时执行的操作是？

Ares = 1 * 3 mod 5 = 3
Bres = 1 * 9 mod 5 = 4
Cres = 1 * 27 mod 5 = 2
Dres = 1 * 81 mod 5 = 1
5判断题

快速幂取模算法只能用于底数a是整数的情况，不能用于模数m为非整数的情况。