如何优化统计区间数位和为偶数的数的Python代码，适配10亿级大数字场景？

原有暴力实现的时间复杂度为O((b-a)*数字位数)，当a、b达到10亿级别时，循环次数最多可达10亿次，总运算量高达百亿级，必然出现执行超时问题。

方案1：数学规律法（最优，仅适用于当前需求） #

我们可以利用数位和的奇偶变化规律直接计算，时间复杂度仅为O(数字位数)，完全适配10亿甚至更大的数值范围：

• 定义函数count_even(x)：统计从0到x中数位和为偶数的自然数个数
• 最终结果 = count_even(b) - count_even(a-1)
• 规律说明：从0开始，数位和的奇偶性整体呈现交替变化特征，最终偶数个数可以通过(x+1 + 数位和奇偶标记) // 2直接计算，其中数位和为偶数时标记为1，奇数时标记为0。

对应实现代码：

def get_digit_parity(x):
    # 返回x的数位和的奇偶性，0为偶，1为奇
    parity = 0
    while x:
        parity += x % 10
        x = x // 10
    return parity % 2

def count_even(x):
    if x < 0:
        return 0
    parity = get_digit_parity(x)
    # 数位和为偶时加1，否则加0，再整除2
    return (x + 1 + (1 if parity == 0 else 0)) // 2

a, b = map(int, input().split())
print(count_even(b) - count_even(a - 1))

方案2：数位动态规划（通用方案，可扩展到其他数位统计需求） #

如果后续需要修改需求（比如统计数位和为某个固定值、数位包含特定数字等），可以使用通用的数位DP解法，时间复杂度同样为O(数字位数)，支持1e18级别的数值计算：
核心思路是通过记忆化搜索遍历所有合法数字，避免重复计算，实现代码如下：

def count_even_digit_sum(x):
    if x < 0:
        return 0
    s = str(x)
    n = len(s)
    from functools import lru_cache
    
    @lru_cache(maxsize=None)
    def dp(pos, is_limit, parity):
        # pos：当前处理到第几位；is_limit：前面的位是否和x的前缀完全一致（决定当前位上限）；parity：当前数位和奇偶性
        if pos == n:
            return 1 if parity == 0 else 0
        upper = int(s[pos]) if is_limit else 9
        total = 0
        for d in range(upper + 1):
            total += dp(pos + 1, is_limit and d == upper, (parity + d) % 2)
        return total
    return dp(0, True, 0)

a, b = map(int, input().split())
print(count_even_digit_sum(b) - count_even_digit_sum(a - 1))

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