3345. Smallest Divisible Digit Product I

題目 / Problem

中文： 給你兩個整數 n 和 t。請回傳一個「大於或等於 n」的最小數字，並且這個數字的各位數字乘積能被 t 整除。

English: You are given two integers n and t. Return the smallest number greater than or equal to n such that the product of its digits is divisible by t.

Constraints / 限制： - 1 <= n <= 100 - 1 <= t <= 10

Worked example / 範例： - Input: n = 15, t = 3 - Output: 16 - 解釋：從 15 開始往上找。15 的數字乘積是 1 × 5 = 5，5 不能被 3 整除。16 的數字乘積是 1 × 6 = 6，6 能被 3 整除，所以答案是 16。

名詞解釋 / Glossary

• 各位數字乘積 / digit product： 把一個數字的每一位數字相乘。例如 234 的數字乘積是 2 × 3 × 4 = 24。特別注意：只要有一位是 0，整個乘積就是 0。/ Multiply every individual digit of a number together. Note that a single 0 digit makes the whole product 0.
• 整除 / divisible： 「a 能被 b 整除」代表 a 除以 b 沒有餘數，也就是 a % b == 0。/ "a is divisible by b" means a divided by b leaves no remainder, i.e. a % b == 0.
• 取餘數運算子 % / modulo operator %： 回傳除法後的餘數。例如 6 % 3 == 0、5 % 3 == 2。/ Returns the remainder after division.
• 暴力枚舉 / brute force enumeration： 不用聰明技巧，直接一個一個把候選答案試過去，找到第一個符合條件的就回傳。/ Instead of a clever trick, just try each candidate one by one and return the first that works.
• 0 是任何數的倍數 / 0 is a multiple of every number： 因為 0 % t == 0 對任何 t 都成立。這一點是本題的關鍵。/ Because 0 % t == 0 holds for any t — a key fact here.

思路

中文：這題的資料範圍很小（n <= 100），而且提示也明講「最多只需要檢查 10 個數字」，所以最直接的暴力枚舉就是最好的解法。我們從 n 開始，一個一個往上試：對每個候選數字 x，先算出它的各位數字乘積，再檢查這個乘積能不能被 t 整除；只要找到第一個符合的，就立刻回傳。要算數字乘積，我們反覆用 x % 10 取出最右邊那一位，乘進累積變數，再用 x / 10（整數除法）把那一位去掉，直到 x 變成 0。為什麼這個做法一定會停下來、而且不用擔心找不到答案？因為只要某個數字包含 0 這一位（例如 10、20），它的數字乘積就是 0，而 0 能被任何 t 整除，所以答案一定存在且很快就會出現，最多往上找幾步就會碰到一個帶 0 的數字。

English: The input range is tiny (n <= 100) and the hint explicitly says we check at most 10 numbers, so plain brute-force enumeration is the right tool — no cleverness needed. Start at n and walk upward one integer at a time. For each candidate x, compute the product of its digits, then test whether that product is divisible by t; return the very first candidate that passes. To get the digit product, repeatedly take the last digit with x % 10, multiply it into a running accumulator, and drop that digit with integer division x / 10, looping until x reaches 0. Why is termination guaranteed? Any number containing a 0 digit (like 10 or 20) has digit product 0, and 0 is divisible by every t. So a valid answer always exists nearby and the loop stops quickly.

逐步走查 / Walkthrough

以第一個範例 n = 10, t = 2 為例 / Using the first example n = 10, t = 2:

我們從 x = 10 開始。先計算 10 的數字乘積 / We start at x = 10 and compute its digit product:

• 現在檢查 / Now check: product % t = 0 % 2 = 0。餘數為 0，代表能被整除 / remainder is 0, so it is divisible.
• 條件成立，立刻回傳 x = 10 / Condition holds, immediately return x = 10. ✅

答案就是 10，跟預期輸出一致 / The answer is 10, matching the expected output.

Solution — C

// 演算法 / Algorithm:
// 從 n 開始逐一往上枚舉每個整數 x，計算 x 的各位數字乘積，
// 一旦該乘積能被 t 整除就回傳 x。因為帶 0 的數字乘積為 0（0 能被任何 t 整除），
// 答案一定存在且很快出現。
// Enumerate x upward from n, compute the digit product, return the first x
// whose product is divisible by t. A 0 digit guarantees an answer exists nearby.

int smallestNumber(int n, int t) {
    // 從 n 開始，無限往上找，直到 return 為止
    // Start at n and loop upward forever until we return.
    for (int x = n; ; x++) {
        long long product = 1;   // 乘積初始化為 1（乘法單位元）/ init product to 1 (multiplicative identity)
        int cur = x;             // 用一個副本來拆解位數，保留原本的 x / a copy of x to peel digits from, keeping x intact

        // 反覆取出最右邊一位並乘進 product，直到 cur 變成 0
        // Repeatedly take the last digit and multiply it in, until cur becomes 0.
        while (cur > 0) {
            product *= cur % 10;  // cur % 10 是最右一位；乘進累積乘積 / cur % 10 is the last digit; multiply it in
            cur /= 10;            // 整數除法去掉最右一位（如 123 -> 12）/ integer division drops the last digit (123 -> 12)
        }

        // 若數字乘積能被 t 整除（餘數為 0），x 就是答案
        // If the digit product is divisible by t (remainder 0), x is the answer.
        if (product % t == 0)
            return x;            // 回傳第一個符合的數字 / return the first matching number
    }
}

Solution — C++

// 演算法 / Algorithm:
// 從 n 開始逐一往上枚舉每個整數 x，計算各位數字乘積，
// 回傳第一個乘積能被 t 整除的 x。帶 0 的數字保證答案存在。
// Enumerate x upward from n, compute digit product, return the first x whose
// product is divisible by t. A 0 digit guarantees an answer exists nearby.

class Solution {
public:
    int smallestNumber(int n, int t) {
        // 從 n 開始，一直往上枚舉，直到 return / enumerate upward from n until we return
        for (int x = n; ; ++x) {
            long long product = 1;  // 乘積初始化為 1 / init product to 1 (multiplicative identity)

            // 用副本 cur 逐位拆解 x，保留 x 本身
            // Use a copy `cur` to peel digits, leaving x untouched.
            for (int cur = x; cur > 0; cur /= 10)   // cur /= 10 每輪去掉最右一位 / drop the last digit each round
                product *= cur % 10;                // cur % 10 是最右一位，乘進 product / last digit, multiplied in

            // product % t == 0 代表能被整除；找到就回傳
            // product % t == 0 means divisible; return once found.
            if (product % t == 0)
                return x;   // 第一個符合條件的數字即為最小答案 / the first match is the smallest answer
        }
    }
};

複雜度 / Complexity

• Time: O(1) — 因為 n <= 100、t <= 10，最多往上檢查約 10 個數字，每個數字最多 3 位。這是一個由題目限制界定的常數量的工作，所以是常數時間。若以一般化角度看，設答案與 n 的距離為 k、數字位數為 d，則是 O(k·d)。/ With n <= 100, we check at most ~10 candidates, each with at most 3 digits — a constant amount of work bounded by the constraints. Generally it is O(k·d) where k is the gap to the answer and d the digit count.
• Space: O(1) — 只用了 product、cur、x 幾個變數，沒有配置任何額外的陣列或容器。/ Only a few scalar variables (product, cur, x); no arrays or containers allocated.

Pitfalls & Edge Cases

• 含 0 的數字乘積是 0 / A 0 digit makes the product 0： 例如 n = 10 的乘積是 1 × 0 = 0。因為 0 % t == 0 對任何 t 成立，這種數字必定符合條件——這正是範例 1 的答案，也是為什麼答案永遠存在。/ E.g. 10 gives product 0, and 0 % t == 0 for any t, so it always qualifies — this is why an answer always exists.
• product 要初始化成 1 而不是 0 / Initialize product to 1, not 0： 乘法的單位元是 1；若初始化成 0，任何數的乘積都會被錯誤地變成 0。/ 1 is the multiplicative identity; starting at 0 would wrongly zero out every product.
• 不要漏掉最左邊的位 / Don't drop the leading digit： while (cur > 0) 迴圈會一直跑到 cur 變 0，確保每一位都被乘到，不會少算最高位。/ The while (cur > 0) loop runs until cur is 0, ensuring every digit — including the highest — is included.
• t = 1 的情況 / When t = 1： 任何整數乘積都能被 1 整除（anything % 1 == 0），所以會直接回傳 n 本身。程式碼自然處理這點，不需特判。/ Every product is divisible by 1, so n itself is returned; the code handles this without a special case.
• 不要用 int 累積乘積怕溢位（本題不會）/ Overflow： 本題數字很小不會溢位，但我們仍用 long long 存 product 作為好習慣，避免在更大範圍的變體題中出錯。/ Values here are tiny so int would suffice, but we use long long for product as a safe habit for larger variants.
• 回傳值別搞混 / Return-value confusion： 要回傳的是候選數字 x 本身，而不是它的數字乘積 product。/ Return the candidate x, not its digit product product.