2025-05-31：最小可整除数位乘积Ⅰ 用go语言，给定两个整数 n 和

摘要：问题理解：• 给定两个整数 n 和 t，需要找到不小于 n 的最小整数，使得该整数的各位数字的乘积能被 t 整除。• 例如，n = 15，t = 3，需要找到 ≥15 的最小整数，其各位数字乘积能被 3 整除。15 的乘积是 1*5=5，不能被 3 整除；16

2025-05-31：最小可整除数位乘积Ⅰ。用go语言，给定两个整数 n 和 t，要求找出不小于 n 的最小整数，使得这个整数各位数字的乘积能够被 t 整除。

输入：n = 15, t = 3。

输出：16。

解释：

16 的数位乘积为 6 ，可以被 3 整除，所以它是大于等于 15 且满足题目要求的最小整数。

题目来自力扣3345。

1. 问题理解：• 给定两个整数 n 和 t，需要找到不小于 n 的最小整数，使得该整数的各位数字的乘积能被 t 整除。• 例如，n = 15，t = 3，需要找到 ≥15 的最小整数，其各位数字乘积能被 3 整除。15 的乘积是 1*5=5，不能被 3 整除；16 的乘积是 1*6=6，能被 3 整除，因此答案是 16。2. 算法思路：• 从 i = n 开始，逐个检查每个整数 i 是否满足条件。• 对于每个 i，计算其各位数字的乘积：• 初始化 prod = 1。• 通过循环取出 i 的每一位数字（从个位开始），并将 prod 乘以该数字。• 检查 prod 是否能被 t 整除：• 如果能，则返回当前的 i。• 如果不能，则继续检查 i+1。3. 具体步骤（以 n = 15，t = 3 为例）：• 初始 i = 15：• 计算乘积：1 * 5 = 5。• 5 % 3 = 2 ≠ 0，不满足。• i = 16：• 计算乘积：1 * 6 = 6。• 6 % 3 = 0，满足条件，返回 16。4. 边界情况：• 如果 n = 0（但题目中 n ≥ 1，无需考虑）。• 如果 t = 1，任何数字的乘积都能被 1 整除，直接返回 n。• 如果 n 本身已经满足条件（如 n = 12，t = 2，1*2=2 能被 2 整除），直接返回 n。5. 终止条件：• 由于题目保证 n 和 t 的范围较小（n ≤ 100，t ≤ 10），算法一定会在有限步内终止。• 时间复杂度：• 最坏情况下需要检查 O(M) 个数字，其中 M 是从 n 开始到第一个满足条件的数字的距离。• 对于每个数字，计算其各位数字的乘积的时间复杂度是 O(d)，其中 d 是数字的位数（最多 3 位，因为 n ≤ 100）。• 因此，总时间复杂度是 O(M * d)，可以认为是 O(M)，因为 d 很小。• 由于 n 和 t 的范围很小，M 的最大值不会很大（例如，n = 99，t = 10，需要检查到 100，M = 2）。• 空间复杂度：• 只使用了常数级别的额外空间（如 prod、循环变量等），因此空间复杂度是 O(1)。package mainimport ( "fmt")func smallestnumber(n, t int)int { for i := n; ; i++ { prod := 1 for x := i; x > 0; x /= 10 { prod *= x % 10 } if prod%t == 0 { return i } }}func main { n := 15 t := 3 result := smallestNumber(n, t) fmt.Println(result)}

# -*-coding:utf-8-*-def smallest_number(n, t):i = nwhile True:prod = 1x = iwhile x > 0:prod *= x % 10x //= 10if prod % t == 0:return ii += 1if __name__ == "__main__":n = 15t = 3result = smallest_number(n, t)print(result)