大指数幂取模程序执行超时，如何优化提升运行效率？

问题分析 #

你的代码采用了最朴素的循环乘法实现幂运算，时间复杂度为O(n)。当指数n是极大数值（比如10^10甚至更大）时，循环次数会呈线性增长，直接导致程序运行超时。

优化方案：快速幂算法（二进制幂） #

快速幂的核心是将指数n拆解为二进制形式，通过不断平方底数来减少乘法次数，时间复杂度降至O(log₂n)——哪怕n是10^18，也只需要约60次循环就能完成计算，效率提升极其明显。

快速幂核心逻辑 #

1. 初始化结果为1，先对底数a取模（避免初始值过大溢出）
2. 当指数n大于0时：
   • 如果n的二进制最后一位是1，将结果与当前底数相乘后取模
   • 将当前底数平方后取模
   • 将指数n右移一位（等价于除以2）

修改后的代码 #

#include <stdio.h>

const long long MOD = 1000000007;

// 快速幂函数：计算 (base^exponent) % MOD
long long fast_power(long long base, long long exponent) {
    long long result = 1;
    base = base % MOD; // 提前取模，防止溢出
    while (exponent > 0) {
        // 指数为奇数时，将结果乘上当前底数
        if (exponent % 2 == 1) {
            result = (result * base) % MOD;
        }
        // 底数平方，指数折半
        base = (base * base) % MOD;
        exponent /= 2;
    }
    return result;
}

int main() {
    int t;
    scanf("%d", &t);
    
    for (int i = 1; i <= t; i++) {
        long long a, n;
        scanf("%lld %lld", &a, &n);
        long long total = fast_power(a, n);
        printf("Case #%d: %lld\n", i, total);
    }
    return 0;
}

代码说明 #

• 将MOD定义为全局常量，避免每次循环重复初始化
• 封装独立的fast_power函数，代码结构更清晰且便于复用
• 每一步乘法后都取模，确保数值始终在long long的范围内，避免溢出
• 也可以用exponent >>= 1替代exponent /= 2，二者效果一致，位运算效率略高

额外健壮性优化 #

可以提前处理特殊场景：

• 当底数a为0时，结果直接返回0
• 当指数n为0时，结果直接返回1（若题目允许n为0的情况）

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