闭区间内幸运数字统计Python算法出错，请求排查修正

问题描述 #

幸运数字定义为：包含数字6或8，但不同时包含6和8的数字。需要统计闭区间[l, r]内的幸运数字数量。原代码尝试用排除法实现，但输入L=1、R=10时输出-34，预期结果为2（数字6和8）。

原代码错误点 #

1. 辅助函数逻辑完全错误 #

原代码中的nums_without_digit和nums_without_digits函数的计算逻辑根本无法统计区间内不含指定数字的数的数量。例如nums_without_digit中循环遍历i并累加(r//10**i)-(l-1)//10**i，这是完全错误的计算方式，无法得到正确的不含指定数字的数的数量。

2. 排除逻辑不符合容斥原理 #

原代码的减法逻辑混乱：

total = r - l + 1
total -= nums_without_digit(l, r, 6)
total -= nums_without_digit(l, r, 8)
total -= nums_without_digits(l, r, 6, 8)

这完全不符合容斥原理，导致结果出现负数。

正确实现思路 #

利用容斥原理计算：

• 幸运数字数量 = (含6的数的数量 + 含8的数的数量) - 2 × 同时含6和8的数的数量

其中：

• 含6的数的数量 = 总数量 - 不含6的数的数量
• 含8的数的数量 = 总数量 - 不含8的数的数量
• 同时含6和8的数的数量 = 总数量 - 不含6的数的数量 - 不含8的数的数量 + 既不含6也不含8的数的数量（容斥原理）

修复后的代码 #

首先实现一个辅助函数，计算小于等于n的数中，不包含指定禁止数字的数量：

def count_without(n, forbidden):
    s = str(n)
    length = len(s)
    count = 0
    # 计算位数小于length的符合条件的数
    for i in range(1, length):
        count += (9 - len(forbidden)) * (9 - len(forbidden)) ** (i - 1)
    # 计算位数等于length的符合条件的数
    for i in range(length):
        has_smaller = False
        for d in range(0 if i > 0 else 1, int(s[i])):
            if d not in forbidden:
                count += (9 - len(forbidden)) ** (length - i - 1)
                has_smaller = True
        if int(s[i]) in forbidden:
            break
        if i == length - 1:
            count += 1
    return count

def count_in_range(l, r, forbidden):
    return count_without(r, forbidden) - count_without(l-1, forbidden)

l, r = map(int, input().split())
total = r - l + 1
without_6 = count_in_range(l, r, {6})
without_8 = count_in_range(l, r, {8})
without_6_8 = count_in_range(l, r, {6, 8})

# 计算幸运数字数量
lucky = (total - without_6) + (total - without_8) - 2 * (total - without_6 - without_8 + without_6_8)
print(lucky)

测试验证 #

输入1 10：

• 总数量：10
• 不含6的数：9（1-5,7-10）
• 不含8的数：9（1-7,9-10）
• 既不含6也不含8的数：8（1-5,7,9-10）
  代入公式：
  (10-9)+(10-9) -2*(10-9-9+8) = 1+1 -2*(0) = 2，与预期结果一致。

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