题目描述

给你一个字符串 num，表示一个 正 整数，同时给你一个整数 t。

如果一个整数 没有 任何数位是 0，那么我们称这个整数是 无零 数字。

请你返回一个字符串，这个字符串对应的整数是大于等于 num 的 最小无零 整数，且 各数位之积 能被 t 整除。如果不存在这样的数字，请你返回 "-1"。

样例

输入：num = "1234", t = 256

输出："1488"

解释：

大于等于 1234 且能被 256 整除的最小无零整数是 1488，它的数位乘积为 256。

输入：num = "12355", t = 50

输出："12355"

解释：

12355 已经是无零且数位乘积能被 50 整除的整数，它的数位乘积为 150。

输入：num = "11111", t = 26

输出："-1"

解释：

不存在大于等于 11111 且数位乘积能被 26 整除的整数。

限制

• 2 <= num.length <= 2 * 10^5
• num 只包含 ['0', '9'] 之间的数字。
• num 不包含前导 0。
• 1 <= t <= 10^14

算法

(贪心，分类讨论) $O(n|\Sigma| + \log t)$

1. $t$ 必须是 2、3、5、7 这四个质因数组成的数字，否则答案为 $-1$。
2. 实现一个判定函数，给定所需要的质因数 2、3、5、7 的数量，以及可以任意填充数字的数位个数，判断是否能满足要求。
   • 质因数 5 和 7 需要固定用数字 5 和 7 来填充。
   • 质因数 3，优先用 9 来填充，其次用 3 来填充。
   • 质因数 2，优先用 8 来填充，其次用 4 来填充，其次用 2 来填充。
   • 如果有一个 2 和一个 3，则用 6 来填充。
3. 从高位开始往低位遍历，如果发现了数字 0，则可以将这个数位修改为 1，然后用上面的判定函数判断后缀数位能否符合要求。如果符合，则停止并构造答案输出。
4. 如果上述过程不能满足要求，此时已经将所有的 0 修改为了 1，则从最低位开始往最高位遍历，寻找需要修改的最小后缀。
5. 寻找的过程就是不断尝试增加当前位的数字，使用判定函数判断后缀数位能否符合要求。如果符合，则停止遍历并构造答案输出。
6. 构造答案也是按照判断函数的规则。注意，构造的答案需要有一个最少长度限制，如果不满足长度限制要求，则需要用 1 来补全。

时间复杂度

• 分解质因数的时间复杂度为 $O(\log t)$。
• 判定函数的时间复杂度为常数。
• 从高位开始往低位遍历一次，时间复杂度为 $O(n)$。
• 从低位往高位遍历并尝试一次，时间复杂度为 $O(n|\Sigma|)$，其中 $|\Sigma|$ 为可能的数字数量，这里为 $9$。
• 故总时间复杂度为 $O(n|\Sigma| + \log t)$。

空间复杂度

• 需要 $O(n + |\Sigma|)$ 的额外空间存储答案和构造答案的临时数组。

C++ 代码

#define LL long long

struct F {
    int f2, f3, f5, f7;

    F() {
        f2 = f3 = f5 = f7 = 0;
    }

    void update(char c, int d) {
        if (c == '2') f2 += d;
        else if (c == '3') f3 += d;
        else if (c == '4') f2 += 2 * d;
        else if (c == '5') f5 += d;
        else if (c == '6') f2 += d, f3 += d;
        else if (c == '7') f7 += d;
        else if (c == '8') f2 += 3 * d;
        else if (c == '9') f3 += 2 * d;

        if (f2 < 0) f2 = 0;
        if (f3 < 0) f3 = 0;
        if (f5 < 0) f5 = 0;
        if (f7 < 0) f7 = 0;
    }

    bool operator >= (const F &t) const {
        return f2 >= t.f2 && f3 >= t.f3 && f5 >= t.f5 && f7 >= t.f7;
    }
};

class Solution {
private:
    bool check(const F &tot, int d, const F &target) {
        d -= max(0, target.f5 - tot.f5);
        if (d < 0)
            return false;

        d -= max(0, target.f7 - tot.f7);
        if (d < 0)
            return false;

        int d3 = max(0, target.f3 - tot.f3);
        if (d < d3 / 2)
            return false;

        d -= d3 / 2;
        d3 %= 2;

        int d2 = max(0, target.f2 - tot.f2);
        if (d < d2 / 3)
            return false;

        d -= d2 / 3;
        d2 %= 3;

        if (d3 == 1) {
            if (d2 <= 1) d -= 1;
            else if (d2 == 2) d -= 2;
        } else {
            if (d2 > 0) d -= 1;
        }

        return d >= 0;
    }

    string build_ans(string &num, int p, F &target) {
        const int n = num.size();

        for (int i = 0; i < p; i++)
            target.update(num[i], -1);

        num.resize(p);

        vector<int> cnt(10, 0);
        cnt[7] = target.f7;
        cnt[5] = target.f5;
        cnt[9] = target.f3 / 2;
        target.f3 %= 2;
        cnt[8] = target.f2 / 3;
        target.f2 %= 3;
        if (target.f3 == 1) {
            if (target.f2 == 0) ++cnt[3];
            else if (target.f2 == 1) ++cnt[6];
            else ++cnt[2], ++cnt[6];
        } else {
            if (target.f2 == 1) ++cnt[2];
            else if (target.f2 == 2) ++cnt[4];
        }

        // 补全 1
        cnt[1] = n - p;
        if (p == 0)
            ++cnt[1];

        for (int c = 2; c <= 9; c++)
            cnt[1] -= cnt[c];

        for (int c = 1; c <= 9;) {
            if (cnt[c] <= 0) ++c;
            else num += c + '0', --cnt[c];
        }

        return num;
    }

public:
    string smallestNumber(string num, LL t) {
        const int n = num.size();
        F target;

        while (t % 2 == 0) ++target.f2, t /= 2;
        while (t % 3 == 0) ++target.f3, t /= 3;
        while (t % 5 == 0) ++target.f5, t /= 5;
        while (t % 7 == 0) ++target.f7, t /= 7;

        if (t > 1)
            return "-1";

        F tot;
        for (int i = 0; i < n; i++) {
            tot.update(num[i], 1);
            // 从高位到低位遍历时遇到了 0，则可以判断将这个数字修改为 1 后，后缀是否可以满足条件
            if (num[i] == '0') {
                num[i] = '1';
                if (check(tot, n - i - 1, target))
                    return build_ans(num, i + 1, target);
            }
            // 如果不满足，则也将这个数位先修改为 1
        }

        // 当前数字已经满足了要求
        if (tot >= target) 
            return num;

        int p = 0;
        for (int i = n - 1; i >= 0; i--) {
            // 尝试替换当前位置的数字
            tot.update(num[i], -1);

            for (char c = num[i] + 1; c <= '9'; c++) {
                tot.update(c, 1);

                if (check(tot, n - i - 1, target)) {
                    // 替换后，满足了要求，则找到了需要修改的最小后缀
                    num[i] = c;
                    p = i + 1;

                    break;
                }

                tot.update(c, -1);
            }

            if (p != 0)
                break;
        }

        return build_ans(num, p, target);
    }
};