如何降低该模幂循环的时间复杂度？解决O(n)导致的TLE问题

这个问题太典型了——当指数大到1e18这种天文数字时，线性循环的O(N)复杂度完全扛不住，必须换成**快速幂（Binary Exponentiation）**算法，把时间复杂度直接降到O(logN)，轻松解决TLE问题！

为啥原来的循环不行？ #

你原来的代码是每次把count乘以10再取模M，要执行N-2次。当N是1e18时，这个循环次数是1e18级别，哪怕计算机每秒跑1e8次操作，也得跑上千年，不超时才怪！

快速幂的核心思路 #

快速幂的本质是利用指数的二进制分解，把大指数的幂运算拆成若干次平方和乘法的组合。比如要算10^k（这里k=N-2），我们可以把k写成二进制形式，比如k=5（二进制101），那10^5 = 10^(4+1) = 10^4 * 10^1。这样只需要计算log₂(k)次操作，对于1e18来说，log₂(1e18)大概是60次，完全在计算机的处理能力范围内。

同时，我们要结合模运算的性质：(a*b) % M = [(a%M) * (b%M)] % M，这样每一步运算都取模，既能保证结果正确，又能避免数值溢出。

具体代码实现 #

你可以把原来的循环替换成一个快速幂函数的调用。下面是C++版本的实现（其他语言思路完全一致）：

首先实现快速幂函数：

// 计算 (base^exp) % mod 的结果
long long pow_mod(long long base, long long exp, long long mod) {
    long long result = 1;
    base = base % mod; // 先对base取模，防止初始值过大溢出
    while (exp > 0) {
        // 如果当前指数的二进制位是1，就把结果乘上当前base
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        // base平方，对应二进制位左移一位
        base = (base * base) % mod;
        exp = exp / 2; // 指数右移一位，相当于除以2
    }
    return result;
}

然后替换原来的循环：

// 原来的循环：for(i=0;i<N-2;i++) count=(count*10)%M;
// 替换成：
if (N >= 2) {
    long long exponent = N - 2;
    count = (count * pow_mod(10, exponent, M)) % M;
}
// 当N<=2时，exponent<=0，10^0=1，count不变，所以可以不用额外处理

额外注意点 #

• 当N-2为0时（也就是N=2），10^0=1，count保持不变，这个函数会自动返回1，所以不需要额外判断（加个判断也没问题，逻辑更清晰）。
• 因为M是1e9+7，属于较大的数，所以要使用64位整数类型（比如C++的long long）来存储中间结果，避免溢出。

这样修改后，你的代码时间复杂度就从O(N)降到了O(logN)，哪怕N是1e18，也只需要几十次循环就能完成，绝对不会超时啦！

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