3345.最小可整除数位乘积 I：暴力枚举（从n开始尝试）

【LetMeFly】3345.最小可整除数位乘积 I：暴力枚举（从n开始尝试）

力扣题目链接：https://leetcode.cn/problems/smallest-divisible-digit-product-i/

给你两个整数 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

解题方法：从n开始尝试

从$n$开始递增枚举，如果当前数字每一位只积是$t$的倍数，则返回。

最多枚举$10$个数一定会出现一个$0$，$0$一定是$t$的倍数。

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

AC代码

C++

/*
 * @LastEditTime: 2026-08-06 15:21:51
 */
class Solution {
private:
    bool ok(int n, int t) {
        int mul = 1;
        while (n) {
            mul *= n % 10;
            n /= 10;
        }
        return mul % t == 0;
    }
public:
    int smallestNumber(int n, int t) {
        while (!ok(n, t)) {
            n++;
        }
        return n;
    }
};

Python

'''
LastEditTime: 2026-08-06 15:24:33
'''
class Solution:
    def smallestNumber(self, n: int, t: int) -> int:
        while True:
            mul = 1
            for i in str(n):
                mul *= ord(i) - ord('0')
            if mul % t == 0:
                return n
            n += 1

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源