如何优化代码处理n≤100、a,b≤10^5的区间数字各位和计算？

原代码超时的核心原因是逐个遍历a到b的所有数字并计算各位和，当a、b差距较大时（比如a=1，b=10^5），循环次数可达10万次，时间复杂度O((b-a+1)*位数)，无法满足时间要求。

优化思路是使用数学方法直接计算0到x的各位数字之和，再通过sum(b) - sum(a-1)得到a到b的结果，将时间复杂度降至O(数字位数)，大幅提升效率。

优化后的代码 #

def sum_digits_up_to(n):
    total = 0
    pow10 = 1
    while pow10 <= n:
        divisor = pow10 * 10
        high = n // divisor
        current = (n // pow10) % 10
        low = n % pow10
        
        # 完整周期的贡献：每个周期内当前位0-9各出现pow10次，总和为45*pow10（0-9的和是45）
        total += high * 45 * pow10
        
        # 剩余部分中，当前位从0到current-1的数字和
        total += (current - 1) * current // 2 * pow10
        
        # 剩余部分中当前位等于current的数字和
        total += current * (low + 1)
        
        pow10 *= 10
    return total

def main():
    n = int(input())
    for _ in range(n):
        a, b = map(int, input().split())
        # 计算a到b的各位和：0到b的和 减去 0到a-1的和
        result = sum_digits_up_to(b) - sum_digits_up_to(a - 1)
        print(result)

if __name__ == "__main__":
    main()

代码逻辑说明 #

sum_digits_up_to(n)函数通过逐位计算每一位数字的总贡献：

1. 完整周期：将数字按当前位的位权（如个位1、十位10）划分为多个完整周期，每个周期内当前位0-9各出现pow10次，总和为high * 45 * pow10。
2. 剩余部分（0到current-1）：计算当前位从0到current-1的数字总和，乘以该位出现的次数pow10。
3. 剩余部分（current）：计算当前位等于current的所有数字的贡献，次数为low + 1（低位的所有可能数+当前数本身）。

这种方法最多循环数字的位数次（10^5仅需6次循环），即使N=100，总循环次数也仅600次，完全不会超时。

内容的提问来源于stack exchange，提问作者Trung The Shrimp