模运算分配律与大指数幂取模求助：优化C++循环代码过1秒时限

问题根源 #

你的普通循环实现是O(n)时间复杂度，当指数是1e9这种超大数时，循环要跑近1e9次，远远超过1秒的时间限制（一般1秒最多跑1e8次左右）。另外你的代码还有个致命逻辑错误：第一个循环修改了变量a的值（把它变成了a^b mod mod），第二个循环的指数用的是修改后的a，而不是输入的原始a，这完全偏离了需求。

模运算的关键性质（为什么能每步取模） #

核心公式：(a * b) % mod = [(a % mod) * (b % mod)] % mod
幂运算本质是多次乘法，所以a^b mod mod可以拆解成多次乘法后取模，每一步取模既不会改变最终结果，还能避免数值溢出（比如long long相乘可能超过64位范围，取模后数值保持在mod以内，不会溢出）。

优化方案：快速幂取模（O(logn)时间） #

快速幂的思路是把指数拆成二进制，通过平方来快速累积结果，比如计算base^exp：

• 初始化结果res = 1
• 当exp > 0时：
  • 如果exp是奇数，就把当前base乘到res里，然后取模
  • 把base平方，然后取模
  • 把exp除以2（右移一位）
    这样循环次数是指数的二进制位数，比如exp=1e9时，只需要约30次循环，完全不会超时。

修正后的完整代码 #

先写一个通用的快速幂函数，然后分别计算三个结果，最后排序输出：

#include <iostream>
#include <algorithm> // 用于sort函数
#include <cstdlib>   // 用于abs函数

using namespace std;
const long long MOD = 1e9 + 7;

// 快速幂取模函数：计算 (base^exp) % mod
long long pow_mod(long long base, long long exp, long long mod) {
    long long res = 1;
    base = base % mod; // 先把base取模，防止初始值过大
    while (exp > 0) {
        // 如果指数是奇数，乘上当前base
        if (exp % 2 == 1) {
            res = (res * base) % mod;
        }
        // base平方，指数除以2
        base = (base * base) % mod;
        exp = exp / 2;
    }
    return res;
}

int main() {
    long long a, b, c;
    cin >> a >> b >> c;
    long long x = abs(a - b); // 直接用abs函数求绝对值，比if-else简洁

    // 计算三个结果，注意用原始的a、b、c，不要修改原变量
    long long res1 = pow_mod(a, b, MOD);
    long long res2 = pow_mod(b, a, MOD);
    long long res3 = pow_mod(c, x, MOD);

    // 把结果放到数组里排序
    long long arr[] = {res1, res2, res3};
    sort(arr, arr + 3);

    // 按升序输出
    cout << arr[0] << " " << arr[1] << " " << arr[2] << endl;

    return 0;
}

代码说明 #

1. 快速幂函数：通用的幂取模实现，处理所有幂运算需求，避免重复代码
2. 保留原变量：计算时用原始的a、b、c，不会像你的代码那样修改原变量导致逻辑错误
3. 排序输出：用sort函数直接排序数组，比手动比较更简洁
4. 绝对值计算：用abs函数替代if-else，代码更简洁

额外提示 #

• 为什么要先把base取模？因为如果base本身比mod大，比如base=1e9+8，取模后变成1，计算更高效
• 每次乘法后都要取模，防止long long溢出（比如两个1e9的数相乘是1e18，刚好在long long的范围内，但如果继续乘就会溢出，所以每步取模是必要的）

内容的提问来源于stack exchange，提问作者Abdelrahman Mohamed salah