题目描述

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

样例

输入：n = 10, t = 2

输出：10

解释：

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

输入：n = 15, t = 3

输出：16

解释：

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

限制

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

算法

(暴力枚举) $O(1)$

1. 按照题目描述暴力枚举大于等于 $n$ 的整数，直到该整数的各数位之积能被 $t$ 整除。

时间复杂度

• 由于 $0$ 可以被任何数字整除，所以枚举的次数不超过 $9$ 次，故总时间复杂度为 $O(1)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
private:
    int calc(int x) {
        int res = 1;

        while (x) {
            res *= x % 10;
            x /= 10;
        }

        return res;
    }

public:
    int smallestNumber(int n, int t) {
        while (1) {
            if (calc(n) % t == 0)
                break;

            ++n;
        }

        return n;
    }
};