C++如何实现快速幂算法_C++大指数幂运算高效求解模板【数论】

快速幂通过二进制拆分指数将时间复杂度从O(exp)降至O(log exp)，核心是每次底数平方、按位累乘，需用long long防溢出并每步取模；标准迭代模板简洁高效，适用于非负整数指数与整数底数。

快速幂的核心逻辑是二进制拆分指数

直接用 pow(base, exp) 算大指数（比如 exp > 1e9）会超时或溢出，因为它是 O(exp) 的线性乘法。快速幂把指数看作二进制位，每次将底数平方、根据当前位是否为 1 决定是否累乘，时间降到 O(log exp)。

关键点在于：每轮迭代中，base 实际代表的是 base^(2^i)，而 exp 的第 i 位为 1 时，就把这一项乘进结果。

• 必须用 long long 存结果和中间乘积，避免 int 溢出
• 模运算（如取模 MOD）要每步都做，不能只在最后取 —— 否则乘法中间就溢出
• 指数为 0 时直接返回 1（注意：0^0 通常按题意定义，一般不在此模板处理）

带取模的递归写法容易栈溢出，推荐迭代实现

递归版虽然直观，但深度达 ~60 层（log₂(1e18) ≈ 60）虽不算深，但在嵌入式或栈受限环境可能出问题；更重要的是，迭代更易控制模运算时机、也方便扩展为矩阵快速幂。

标准迭代模板如下（以 MOD = 1e9+7 为例）：

立即学习“C++免费学习笔记（深入）”；

Palette

在线生成整套UI调色板

下载

const int MOD = 1e9 + 7;
long long quick_pow(long long base, long long exp) {
    long long res = 1;
    base %= MOD;  // 防止 base 本身超 MOD
    while (exp > 0) {
        if (exp & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return res;
}

• exp & 1 比 exp % 2 == 1 更快且无符号安全
• exp >>= 1 等价于 exp /= 2，但位运算更稳定
• 如果题目不要求取模，去掉所有 % MOD，但仍需保留 long long 和 base %= MOD 的等效检查（如改为 if (base >= MOD) base %= MOD;）

负指数、浮点底数、大数字符串指数都不适用此模板

这个模板只处理「非负整数指数 + 整数底数」场景。遇到以下情况需另作处理：

• 负指数：C++ 原生不支持整数类型的负幂，需转成浮点或配合逆元（仅当模数为质数且底数非倍数时可用费马小定理）
• 底数是 double：快速幂逻辑不变，但要注意精度丢失，尤其指数大时结果可能为 inf 或 nan
• 指数以字符串给出（如长度 1e5 的数字）：不能转 long long，得用高精度取模预处理指数（即计算 exp % phi(MOD)，再套快速幂），这属于数论进阶内容，和本模板无关

矩阵快速幂只需改乘法为矩阵乘

把标量乘法换成 vector> 的乘法，其余结构完全一致。例如求斐波那契第 n 项，转移矩阵是 {{1,1},{1,0}}，快速幂算它 n-1 次方后乘初始向量即可。

唯一额外注意点：矩阵乘法的维度和模运算位置。例如 2×2 矩阵相乘，每项都要 % MOD，且中间用 long long 防止三项乘积累加溢出：

vector> mat_mult(const vector>& A, const vector>& B) {
    int n = A.size(), m = B[0].size(), p = B.size();
    vector> C(n, vector(m, 0));
    for (int i = 0; i < n; i++)
        for (int k = 0; k < p; k++)
            for (int j = 0; j < m; j++)
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
    return C;
}

真正容易漏掉的是：矩阵快速幂的单位矩阵初始化必须对角为 1、其余为 0，且大小要和输入矩阵一致 —— 错一维或少一个 % MOD，结果就全错。