2025-09-17：统计美丽整数的数目用go语言，给定两个正整数 l 和 r

摘要：2025-09-17：统计美丽整数的数目。用go语言，给定两个正整数 l 和 r，统计区间 [l, r]（含端点）内有多少个整数满足这样的条件：把这个数的每一位数字相乘得到的乘积，恰好能被这些位上数字之和整除。返回符合条件的整数个数。

2025-09-17：统计美丽整数的数目。用go语言，给定两个正整数 l 和 r，统计区间 [l, r]（含端点）内有多少个整数满足这样的条件：把这个数的每一位数字相乘得到的乘积，恰好能被这些位上数字之和整除。返回符合条件的整数个数。

输入：l = 10, r = 20。

输出：2。

解释：

范围内的美丽整数为 10 和 20 。

题目来自力扣3490。

1. 问题分析：
题目要求统计区间 [l, r] 内满足条件的整数（称为“美丽整数”）的个数。条件为：整数的各位数字乘积能被各位数字之和整除（即乘积模和等于0）。由于 l 和 r 的范围可能很大（最大到10^9），直接遍历每个数并检查条件会超时，因此需要使用数位动态规划（数位DP）来高效计算。

2. 数位DP设计：

• 将问题转化为计算 [0, r] 的美丽整数个数减去 [0, l-1] 的美丽整数个数（即 calc(r) - calc(l-1)）。

• 数位DP的核心是递归函数dfs(i, m, s, isLimit, isNum)，其中：

• i：当前处理到数字的哪一位（从高位到低位，但实际存储时数字被反转，因此从低位开始处理）。

• m：当前已处理数字位的乘积（初始为1，因为乘积需要乘法单位元1）。

• s：当前已处理数字位的和（初始为0）。

• isLimit：表示之前的位是否都紧贴上界（例如上界是123，前两位选了12，则第三位受限）。

• isNum：表示是否已经开始填数字（避免前导0的影响）。

• 递归函数返回：从第 i 位开始，在受限状态和数字状态下，能构造出的美丽整数数目。

3. 递归过程：

• 如果所有位处理完毕（i

• 使用记忆化缓存（memo）避免重复计算。缓存键为 (i, m, s)，因为这三个状态唯一确定一个子问题（注意：只有当不受限且已开始填数字时才能缓存，因为受限状态可能不同）。

• 当前位的数字上限：如果受限则为原数字对应位的值，否则为9。

• 如果尚未开始填数字（即isNum为false），可以选择跳过（继续不填数字，即保持前导0）。

• 枚举当前位可填的数字d（从0或1开始，到上限hi），递归处理下一位：

• 新乘积 = m * d

• 新和 = s + d

• 新受限状态：当前受限且d等于上限

• 新数字状态：只要填了数字（d>=1）或之前已开始，则isNum为true。

4. 具体例子（l=10, r=20）：

• 计算calc(20) - calc(9)（因为calc(10-1)=calc(9)）。

• 对于数字10：各位乘积=1*0=0，各位和=1+0=1，0能被1整除（0模1为0），因此是美丽整数。

• 对于数字20：乘积=2*0=0，和=2+0=2，0能被2整除，因此是美丽整数。

• 其他数字（11到19）均不满足条件（比如11：乘积=1*1=1，和=1+1=2，1不能被2整除）。

• 因此结果为2。

5. 记忆化缓存优化：

• 状态 (i, m, s) 中，i的最大位数（10^9有10位）为10，m和s的取值范围较大（但实际中乘积和和不会太大，因为数字最多10位，每位最多9，乘积最大为9^10≈3.4e9，但实际递归中很多状态不会出现，且乘积和和的值会被缓存键记录）。

• 由于m和s可能很大，但实际有效的状态数不会太多（因为数字位数有限，且乘积和和的增长有约束），因此记忆化缓存能有效减少重复计算。

• 时间复杂度：
数位DP的时间复杂度主要取决于状态数。状态由 (i, m, s) 组成，其中i最多10位，m和s的取值范围较大，但实际有效的状态数不会太多（因为乘积m和和s虽然理论上很大，但数字位数有限，且递归中只会访问一部分状态）。最坏情况下状态数约为 O(10 * (9^10) * (9*10))，但实际由于约束（如数字位数和上限）和记忆化，效率较高。通常认为数位DP在解决此类问题时是可行的。

• 额外空间复杂度：
主要额外空间是记忆化缓存（memo）使用的空间。缓存键为 (i, m, s)，因此空间复杂度与状态数相同，即 O(10 * (9^10) * (9*10))，但实际中状态数远小于理论值（因为m和s不会同时达到最大，且受限状态不会缓存），因此空间消耗在可接受范围内。

该数位DP通过记忆化递归高效统计了美丽整数的数目，避免了暴力枚举。时间复杂度和空间复杂度均与状态数相关，实际运行效率较高。

package mainimport ( "fmt" "strconv" "slices")type tuple struct{ i, m, s int }var memo = map[tuple]int{}var high bytefunc dfs(i, m, s int, isLimit, isNum bool) (res int) { if i 0 { return0 } return1 } if !isLimit && isNum { t := tuple{i, m, s} if v, ok := memo[t]; ok { return v } deferfunc { memo[t] = res } } hi := 9 if isLimit { hi = int(high[i] - '0') } d := 0 if !isNum { res = dfs(i-1, m, s, false, false) // 什么也不填 d = 1 } // 枚举填数字 d for ; d

# -*-coding:utf-8-*-from typing import Dict, Tuplememo: Dict[Tuple[int,int,int], int] = {}high: list = def dfs(i: int, m: int, s: int, isLimit: bool, isNum: bool) -> int: # i: 当前处理的位索引（从0开始，对应倒序后的位） # m: 已填数字的乘积 # s: 已填数字的和 if i int: if r int: return calc(r) - calc(l-1)if __name__ == "__main__": l = 10 r = 20 print(beautifulNumbers(l, r))