C++快速幂与大数取模算法示例

前言

快速幂（fast exponentiation / binary exponentiation）用来在 O(log n) 次乘法内计算a^n；大数取模则是处理「数字大到无法用内置整数类型表示」时的取模运算。这两个技巧经常一起出现：比如计算a^b mod m，其中b可能有几千位，或者计算一个超长十进制数对m的余数。

常见的误解有三个。第一，以为快速幂必须用递归写；迭代版本同样简单，而且没有栈深度问题。第二，以为「大数取模」只能用高精度整数库；对一个十进制字符串逐位取模就足够了，不需要真的把大数存下来。第三，以为指数很大时可以直接用欧拉定理把指数模掉φ(m)；这个做法只在gcd(a, m) = 1时成立，否则需要额外处理，盲目使用会得到错误结果。

本文先讲快速幂的二进制拆分原理，再讲模运算中的溢出问题，然后给出「字符串大数取模」和「超大指数快速幂」两个实现。代码以 C++17 为基准。

一、快速幂的二进制拆分

要计算a^n，朴素做法是乘n次，复杂度 O(n)。快速幂利用指数的二进制表示：

n = b_k·2^k + ... + b_1·2 + b_0，其中 b_i ∈ {0, 1}
a^n = a^(b_k·2^k) · ... · a^(b_1·2) · a^(b_0)

从低位到高位扫描指数的二进制位，维护当前的base = a^(2^i)，如果第i位是 1，就把base乘进结果；每轮把base平方，得到下一位的权重。乘法次数是 O(log n)。

// 适用于 C++17
long long powMod(long long base, long long exp, long long mod) {
if (mod == 1) return 0; // 任何数模 1 都是 0

long long result = 1 % mod; // mod 为 1 时上面已返回，这里安全
base %= mod;
if (base < 0) base += mod; // 处理负底数

while (exp > 0) {
if ((exp & 1LL) != 0) {
result = (result * base) % mod;
}
base = (base * base) % mod;
exp >>= 1;
}
return result;
}

几个细节：

• 
  
• mod == 1必须单独处理，否则1 % mod会变成除以 0。虽然1 % 1是 0，但base %= mod在mod == 1时没问题，真正的问题在别处：如果直接写result = 1，最后返回 1，而正确答案是 0。提前返回最省事。
• 
  
• exp用long long，因为指数可能很大；如果指数本身是字符串，见第四节。
• 
  
• base * base可能溢出long long。当mod接近10^9时，(mod-1)^2约10^18，小于LLONG_MAX ≈ 9.22×10^18，安全；当mod接近10^18时就会溢出，需要改用__int128或「加法版乘法」。
• 
  
• exp & 1LL而不是exp % 2，位运算更直接，也避免对负数取模的符号问题（这里exp非负，但习惯上仍用位运算）。
• 
  

二、模运算与溢出

模运算的基本性质：

(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a * b) mod m = ((a mod m) * (b mod m)) mod m
(a - b) mod m = ((a mod m) - (b mod m) + m) mod m

加法、乘法可以在每一步取模，保证中间结果不膨胀。减法要加m再取模，避免负数。

真正的风险是乘法溢出。设m = 10^18，两个小于m的数相乘最大约10^36，远超 64 位。三种处理方式：

1. 
   
2. 限制m的范围：若m ≤ 10^9，(m-1)^2 < 10^18，long long足够。这是最常见的情况，写代码时明确说明前提。
3. 
   
4. 使用__int128：GCC/Clang 在 64 位平台提供__int128，可以容纳两个 64 位数的乘积。它不是标准 C++ 类型，MSVC 不支持，移植性差，使用时要加条件编译。
5. 
   
6. 加法版乘法（binary multiplication）：把a * b拆成「加倍 + 累加」，复杂度 O(log b)，不依赖扩展类型。
7. 
   

// 适用于 C++17
// 前提：0 <= a, b < mod，且 mod <= LLONG_MAX / 2
long long mulMod(long long a, long long b, long long mod) {
long long result = 0;
a %= mod;
b %= mod;
while (b > 0) {
if ((b & 1LL) != 0) {
result += a;
if (result >= mod) result -= mod;
}
a += a;
if (a >= mod) a -= mod;
b >>= 1;
}
return result;
}

这里用「加完立刻减mod」代替%，前提是a < mod且result < mod，所以result + a < 2*mod，最多减一次就够。a += a同理。这个前提要求mod <= LLONG_MAX / 2，否则a + a本身就会溢出。如果mod更大，只能借助__int128或高精度。

三、字符串大数取模

给定一个十进制字符串s（可能几千位）和模数m，求s mod m。做法是从左到右扫描，维护当前余数：

r = 0
for each digit d:
r = (r * 10 + d) mod m

原理是s = 10 * prefix + d，而(10 * prefix + d) mod m = ((10 * (prefix mod m)) mod m + d) mod m。每一步只需要保留余数，不需要保存整个大数。

// 适用于 C++17
#include <cctype>
#include <stdexcept>
#include <string>

long long modString(const std::string& s, long long mod) {
if (mod <= 0) {
throw std::invalid_argument("mod must be positive");
}
long long r = 0;
bool hasDigit = false;
for (char ch : s) {
if (ch == '+' || ch == '-') continue; // 简化：忽略符号
if (!std::isdigit(static_cast<unsigned char>(ch))) {
throw std::invalid_argument("non-digit character");
}
hasDigit = true;
r = (r * 10 + (ch - '0')) % mod;
}
if (!hasDigit) {
throw std::invalid_argument("empty number");
}
return r;
}

r * 10同样可能溢出：r < mod，若mod接近10^18，r * 10会超过LLONG_MAX。因此这个实现适用于mod <= LLONG_MAX / 10（约9.2×10^17）。需要支持更大的模数时，把r * 10 + d换成mulMod(r, 10, mod)再加d，或者用__int128。

符号处理这里做了简化：遇到+、-直接跳过。严格来说，负数的余数在数学上有不同定义（C++ 的%对负数返回负余数），如果需要处理负数，应该在结果上做调整，并在文档里写清楚语义。本文只处理非负整数，避免歧义。

四、超大指数的快速幂

如果指数b是一个几千位的十进制字符串，无法存进long long。有两种思路：

思路一：逐位处理指数。设指数的十进制表示为d_1 d_2 ... d_k，则

a^(d_1 d_2 ... d_k) = ((...(a^(d_1))^10 · a^(d_2))^10 · ...)^10 · a^(d_k)

也就是每读一位，把当前结果升到 10 次方，再乘上a^d。因为a^10和a^d（d 是 0 到 9）都可以用快速幂在常数时间内算出，整体复杂度是 O(k · log 10) = O(k)。

// 适用于 C++17
long long powModBigExp(long long base, const std::string& exp, long long mod) {
if (mod == 1) return 0;

long long result = 1 % mod;
base %= mod;
if (base < 0) base += mod;

for (char ch : exp) {
if (ch < '0' || ch > '9') {
throw std::invalid_argument("exponent must be decimal digits");
}
const int digit = ch - '0';
result = powMod(result, 10, mod);
result = (result * powMod(base, digit, mod)) % mod;
}
return result;
}

注意powMod(base, digit, mod)里的digit是 0 到 9，powMod(base, 0, mod)返回1 % mod，符合「乘 1」的语义。result = powMod(result, 10, mod)每轮把已有结果升到 10 次方，对应十进制左移一位。

思路二：欧拉定理降幂。当gcd(a, m) = 1时，a^φ(m) ≡ 1 (mod m)，所以可以把指数对φ(m)取模。计算φ(m)需要分解m，对较大的m并不便宜；而且gcd(a, m) != 1时不能直接这么做（需要扩展欧拉定理，并且要判断指数是否大于φ(m)）。如果对数学细节没有把握，思路一更稳妥：它不依赖任何数论条件，对任意a、m都成立。

五、完整示例

// 适用于 C++17
#include <iostream>
#include <string>

long long powMod(long long base, long long exp, long long mod) {
if (mod == 1) return 0;
long long result = 1 % mod;
base %= mod;
if (base < 0) base += mod;
while (exp > 0) {
if ((exp & 1LL) != 0) result = (result * base) % mod;
base = (base * base) % mod;
exp >>= 1;
}
return result;
}

long long powModBigExp(long long base, const std::string& exp, long long mod) {
if (mod == 1) return 0;
long long result = 1 % mod;
base %= mod;
if (base < 0) base += mod;
for (char ch : exp) {
const int digit = ch - '0';
result = powMod(result, 10, mod);
result = (result * powMod(base, digit, mod)) % mod;
}
return result;
}

int main() {
std::cout << powMod(2, 10, 1000) << '\n'; // 24
std::cout << powMod(3, 0, 7) << '\n'; // 1
std::cout << powMod(5, 3, 1) << '\n'; // 0
std::cout << powModBigExp(2, "10", 1000) << '\n'; // 24
std::cout << powModBigExp(2, "100", 1000) << '\n'; // 2^100 mod 1000 = 376
return 0;
}

2^100 = 1267650600228229401496703205376，末三位是 376，所以2^100 mod 1000 = 376。这个结果可以用十进制乘法手工核对，不依赖程序运行。

六、复杂度

常见坑点

1. 忘记 mod == 1

❌long long result = 1;直接返回，powMod(5, 3, 1)得到 1，正确答案是 0。

✅ 开头if (mod == 1) return 0;。

2. 指数为 0 时返回 0

❌ 循环一次都不执行，result初始化为 0，返回 0。

✅result初始化为1 % mod；任何非零数的 0 次方是 1。

3. 负底数没有归一化

❌base %= mod;后base仍为负，后续乘法结果为负。

✅if (base < 0) base += mod;。

4. 中间乘法溢出

❌mod = 10^18时仍写result * base % mod，long long溢出，UB。

✅ 限制mod范围，或用__int128/mulMod；并在文档里写明前提。

5. 用欧拉定理降幂却不检查互质

❌ 对gcd(a, m) != 1的情况直接用b % φ(m)。

✅ 用逐位处理指数的通用方法，或使用扩展欧拉定理并正确处理「指数是否足够大」。

**6. 大数取模时 r * 10 溢出**

❌mod接近10^18时直接r = (r * 10 + d) % mod。

✅ 用mulMod(r, 10, mod)，或限制mod <= LLONG_MAX / 10。

7. 把字符串里的符号当数字

❌ch - '0'对'-'得到负数，参与运算。

✅ 先判断字符范围，或显式处理符号。

8. 递归实现快速幂导致栈溢出

❌return powMod(base, exp / 2, mod) * ...递归深度 O(log n)，通常不深，但指数类型很大时仍有风险。

✅ 用迭代版本，空间 O(1)。

总结

快速幂和大数取模的共同点是「不把中间结果算到完整大小」：快速幂不真的算a^n，大数取模不真的存下整个大数。理解了这一点，代码就只是几个循环；真正的风险在溢出和边界（mod == 1、指数为 0、负底数），这些才是需要逐条检查的地方。