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

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

1 <= n <= 100。

1 <= t <= 10。

输入：n = 15, t = 3。

输出：16。

解释：

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

题目来自力扣3345。

分步骤描述过程：

1. 1. 问题理解：
   • • 给定两个整数 n 和 t，需要找到不小于 n 的最小整数，使得该整数的各位数字的乘积能被 t 整除。
   • • 例如，n = 15，t = 3，需要找到 ≥15 的最小整数，其各位数字乘积能被 3 整除。15 的乘积是 1*5=5，不能被 3 整除；16 的乘积是 1*6=6，能被 3 整除，因此答案是 16。
2. 2. 算法思路：
   • • 从 i = n 开始，逐个检查每个整数 i 是否满足条件。
   • • 对于每个 i，计算其各位数字的乘积：
     • • 初始化 prod = 1。
     • • 通过循环取出 i 的每一位数字（从个位开始），并将 prod 乘以该数字。
   • • 检查 prod 是否能被 t 整除：
     • • 如果能，则返回当前的 i。
     • • 如果不能，则继续检查 i+1。
3. 3. 具体步骤（以 n = 15，t = 3 为例）：
   • • 初始 i = 15：
     • • 计算乘积：1 * 5 = 5。
     • • 5 % 3 = 2 ≠ 0，不满足。
   • • i = 16：
     • • 计算乘积：1 * 6 = 6。
     • • 6 % 3 = 0，满足条件，返回 16。
4. 4. 边界情况：
   • • 如果 n = 0（但题目中 n ≥ 1，无需考虑）。
   • • 如果 t = 1，任何数字的乘积都能被 1 整除，直接返回 n。
   • • 如果 n 本身已经满足条件（如 n = 12，t = 2，1*2=2 能被 2 整除），直接返回 n。
5. 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)。

Go完整代码如下：

package main

import (
    "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)
}

Python完整代码如下：

# -*-coding:utf-8-*-

defsmallest_number(n, t):
    i = n
    whileTrue:
        prod = 1
        x = i
        while x > 0:
            prod *= x % 10
            x //= 10
        if prod % t == 0:
            return i
        i += 1

if __name__ == "__main__":
    n = 15
    t = 3
    result = smallest_number(n, t)
    print(result)