2025-05-31:最小可整除数位乘积Ⅰ。用go语言,给定两个整数 n 和 t,要求找出不小于 n 的最小整数,使得这个整数各位数字的乘积能够被 t 整除。
1 <= n <= 100。
1 <= t <= 10。
输入:n = 15, t = 3。
输出:16。
解释:
16 的数位乘积为 6 ,可以被 3 整除,所以它是大于等于 15 且满足题目要求的最小整数。
题目来自力扣3345。
n
和 t
,需要找到不小于 n
的最小整数,使得该整数的各位数字的乘积能被 t
整除。n = 15
,t = 3
,需要找到 ≥15
的最小整数,其各位数字乘积能被 3
整除。15
的乘积是 1*5=5
,不能被 3
整除;16
的乘积是 1*6=6
,能被 3
整除,因此答案是 16
。i = n
开始,逐个检查每个整数 i
是否满足条件。i
,计算其各位数字的乘积:prod = 1
。i
的每一位数字(从个位开始),并将 prod
乘以该数字。prod
是否能被 t
整除:i
。i+1
。n = 15
,t = 3
为例):i = 15
:1 * 5 = 5
。5 % 3 = 2 ≠ 0
,不满足。i = 16
:1 * 6 = 6
。6 % 3 = 0
,满足条件,返回 16
。n = 0
(但题目中 n ≥ 1
,无需考虑)。t = 1
,任何数字的乘积都能被 1
整除,直接返回 n
。n
本身已经满足条件(如 n = 12
,t = 2
,1*2=2
能被 2
整除),直接返回 n
。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 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)
}
# -*-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)