CodeChef提交代码显示耗时0秒却触发Time Limit Exceeded错误问询

报错成因 #

• 算法复杂度过高是核心原因：当前代码采用暴力遍历[l, r]范围内所有进制的方案，当区间范围较大时（比如区间长度超过1e4），叠加每次进制转换的O(log n)开销，总运算量会远超Python在题目时间限制内可承载的阈值。显示运行耗时为0秒是因为代码在执行首个大数据测试用例时直接触发超时，系统尚未完成耗时统计就终止了程序。
• 剪枝逻辑效率极低：你设计的stopper剪枝仅在后续进制的数字和超过当前最优值时中断转换，但首次调用转换函数时stopper为无穷大，无任何剪枝效果，且小进制的数字和本身就偏大，剪枝触发的概率极低，无法有效降低运算量。
• 冗余操作占用资源：numberToBase函数中存储所有进制位、再反转求和的操作完全多余，直接累加每一步的余数即可得到数字和，额外的数组操作会拖慢执行速度。
• 输入效率问题为次要影响因素：当测试用例数量Q较大时，反复调用input()函数的开销确实会上升，但这不是本次超时的核心诱因。

优化方案 #

• 替换暴力枚举逻辑：本题不需要遍历所有[l, r]区间内的进制，仅需要枚举候选进制即可：候选集包括n的所有因数、sqrt(n)附近的数值、以及区间边界值，总候选数不超过200个，可将运算量降低几个数量级。
• 简化进制转换函数：删除无用的digits数组，直接返回累加的余数和，代码可修改为：

def numberToBase(n, b, stopper):
    counter = 0
    while n:
        rem = n % b
        counter += rem
        if counter > stopper:
            return float('inf')
        n = n // b
    return counter

• 优化输入读取方式：改用sys.stdin一次性读取所有输入，避免多次IO开销，示例写法：

import sys
data = list(map(int, sys.stdin.read().split()))
ptr = 0
Q = data[ptr]
ptr += 1
for _ in range(Q):
    n = data[ptr]
    l = data[ptr+1]
    r = data[ptr+2]
    ptr +=3
    # 后续业务逻辑

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