README.md

comments	difficulty	edit_url	tags
true	简单	https://github.com/doocs/leetcode/edit/main/solution/3300-3399/3345.Smallest%20Divisible%20Digit%20Product%20I/README.md	数学 枚举

3345. 最小可整除数位乘积 I

English Version

题目描述

给你两个整数 n 和 t 。请你返回大于等于 n 的 最小 整数，且该整数的 各数位之积 能被 t 整除。

 

示例 1：

输入：n = 10, t = 2

输出：10

解释：

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

示例 2：

输入：n = 15, t = 3

输出：16

解释：

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

 

提示：

• 1 <= n <= 100
• 1 <= t <= 10

解法

方法一：枚举

我们注意到，每 $10$ 个数里一定会出现数位乘积为 $0$ 的整数，因此我们可以直接枚举大于等于 $n$ 的整数，直到找到一个数位乘积能被 $t$ 整除的整数。

时间复杂度 $O(\log n)$，空间复杂度 $O(1)$。

Python3

class Solution:
    def smallestNumber(self, n: int, t: int) -> int:
        for i in count(n):
            p = 1
            x = i
            while x:
                p *= x % 10
                x //= 10
            if p % t == 0:
                return i

Java

class Solution {
    public int smallestNumber(int n, int t) {
        for (int i = n;; ++i) {
            int p = 1;
            for (int x = i; x > 0; x /= 10) {
                p *= (x % 10);
            }
            if (p % t == 0) {
                return i;
            }
        }
    }
}

C++

class Solution {
public:
    int smallestNumber(int n, int t) {
        for (int i = n;; ++i) {
            int p = 1;
            for (int x = i; x > 0; x /= 10) {
                p *= (x % 10);
            }
            if (p % t == 0) {
                return i;
            }
        }
    }
};

Go

func smallestNumber(n int, t int) int {
	for i := n; ; i++ {
		p := 1
		for x := i; x > 0; x /= 10 {
			p *= x % 10
		}
		if p%t == 0 {
			return i
		}
	}
}

TypeScript

function smallestNumber(n: number, t: number): number {
    for (let i = n; ; ++i) {
        let p = 1;
        for (let x = i; x; x = Math.floor(x / 10)) {
            p *= x % 10;
        }
        if (p % t === 0) {
            return i;
        }
    }
}