如何优化计算a^b mod 1000000007的代码以避免溢出？

原代码的核心问题 #

• 无限递归：函数开头直接调用power(a,b)，未先处理终止条件，导致程序进入无限递归，最终栈溢出崩溃。
• 逻辑错误：在计算结果前就判断power(a,b)的大小，这完全不成立——必须先完成计算才能判断结果，但此时递归已无限展开。
• 溢出风险：即便递归逻辑正确，a * power(a, b-1)会随b增大快速超出unsigned long long的存储范围，溢出后结果完全错误。
• 冗余判断：判断结果等于1e9+7时返回0是多余操作，直接对1e9+7取模自然会得到0。

优化方案：快速幂+分步取模 #

要解决问题，需利用快速幂算法（二分幂）将时间复杂度从O(b)降至O(log b)，同时结合模运算性质：(x * y) % m = [(x % m) * (y % m)] % m，每一步计算都取模，彻底避免数值溢出。

关键思路 #

1. 快速幂：将指数b拆分为二进制形式，比如b=5（二进制101），则a^5 = a^4 * a^1，通过不断平方底数，根据二进制位决定是否将当前底数累乘到结果中。
2. 分步取模：每次乘法后立即对1e9+7取模，保证数值始终处于unsigned long long的安全存储范围内。
3. 迭代实现：避免递归栈溢出风险，即便b达到1e7，迭代仅需约24次循环，效率与稳定性远高于原递归方案。

修复后的代码 #

#include <stdio.h>
#define MOD 1000000007

unsigned long long power(unsigned long long a, unsigned long long b) {
    unsigned long long result = 1;
    // 先对a取模，避免初始a大于MOD的情况
    a = a % MOD;
    while (b > 0) {
        // 若b为奇数，将当前a乘入结果并取模
        if (b % 2 == 1) {
            result = (result * a) % MOD;
        }
        // 底数平方后取模
        a = (a * a) % MOD;
        // 指数折半
        b = b / 2;
    }
    return result;
}

int main() {
    unsigned long long a, b;
    scanf("%llu %llu", &a, &b);
    printf("%llu", power(a, b));
    return 0;
}

代码解释 #

• 初始取模：先将a对MOD取模，处理a本身大于MOD的情况（比如a=1e9+8，取模后变为1）。
• 循环处理指数：每次将指数b折半，底数a平方并取模；当b为奇数时，把当前a乘入结果并取模。
• 无溢出风险：(a*a)的最大值为(MOD-1)^2 = (1e9+6)^2 ≈ 1e18+1.2e10+36，而unsigned long long的最大值约为1.8e19，完全可以容纳该数值，因此乘法后取模不会溢出。

原递归方案的致命缺陷 #

原递归的时间复杂度为O(b)，当b=1e7时，递归调用次数会达到1e7次，远超默认栈的承载能力（通常仅几MB），必然导致栈溢出；而快速幂迭代版本仅需约24次循环，效率与稳定性碾压原递归。

内容的提问来源于stack exchange，提问作者Fateme