求助：基于动态规划实现区间[a,b]内满足双条件数的高效查找

AI 小北

2026-5-19

这题确实是**数位动态规划（Digit DP）**的经典应用场景——暴力枚举1e11级别的数完全不现实，我给你拆解下具体的解决思路，分情况处理效率会高很多：

核心思路

数位DP的核心是先计算[0, x]范围内满足条件的数的数量，然后通过f(b) - f(a-1)得到[a,b]的结果，把区间问题拆解成两个端点的计算问题。不过因为k的范围可以到1e11，直接用常规DP会有状态爆炸的问题，所以得分情况处理：

1. 先处理k过大的边界情况

当k大到区间里最多只有1个k的倍数时，直接枚举检查比DP快得多：

如果 k > b：
- 只有当a ≤ k ≤ b时，k本身是候选数，计算它的各位数字之和，看是否在[c,d]范围内，符合就输出，否则没有结果。
- 其他情况直接输出空结果。
如果 k > (b - a + 1)：
- 先算出区间里第一个k的倍数：x = ((a + k - 1) // k) * k
- 要是x ≤ b，就检查x的各位和是否在[c,d]，符合就输出x，否则没有结果。

当k小到区间里有多个k的倍数时，就用记忆化搜索版的数位DP来计算。我们定义一个递归函数，跟踪几个关键状态：

我把每个参数的作用用大白话解释下：

终止条件：当所有数位处理完（pos == 总位数）：
- 如果还是前导零状态（也就是数字是0），题目里a≥1，所以不算，返回0。
- 否则检查两个条件：mod == 0（能被k整除）且c ≤ sum_digits ≤ d（各位和在范围内），符合就返回1，否则返回0。
记忆化缓存：如果当前状态之前算过，直接返回缓存的结果（避免重复计算）。
确定当前位的可选数字范围：
- 如果tight是True，当前位最大只能选原数对应位的数字；否则可以选0到9。
遍历所有可能的数字：
- 对每个可能的数字digit，计算新的状态：
  - new_tight：如果之前是tight状态，且当前选的数字等于原数对应位，那新状态还是tight，否则不是。
  - new_leading_zero：如果之前是前导零，且当前选的还是0，那依然是前导零，否则不是。
  - new_sum：如果还是前导零，各位和保持0；否则加上当前digit。
  - new_mod：如果还是前导零，余数保持0；否则用(mod * 10 + digit) % k计算新余数（这样每次都取模，不会出现大数溢出）。
- 把所有可能的digit对应的结果加起来，就是当前状态的总数量。
缓存并返回结果：把当前状态的结果存起来，返回给上一层。

转数位数组：把要计算的数字（比如b或者a-1）转成高位在前的数组，方便逐位处理。
处理a=1的情况：计算f(a-1)就是计算f(0)，此时要注意0不在[a,b]里，所以结果应该是0。
语言选择：Python的整数没有溢出问题，用lru_cache做记忆化很方便；如果用C++这类语言，要注意用64位整数（long long）处理模运算，避免溢出。
状态优化：前导零状态其实可以和sum_digits合并（前导零时sum_digits一定是0），能少一个状态维度，节省内存和计算时间。

计算出f(b)（[0,b]中符合条件的数的数量）和f(a-1)（[0,a-1]中符合条件的数的数量），两者的差就是[a,b]的结果。如果需要列出所有符合条件的数，那在DP过程中要记录符合条件的数字字符串，最后整理输出就行，思路和计数是一致的。

实用小建议

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