2025-06-02：最小可整除数位乘积Ⅱ 用go语言，给定一个表示正整

摘要：检查t的质因子：• 首先，检查 t 是否包含大于 7 的质因子。因为数字的每一位只能是 1-9，所以乘积的质因子只能是 2、3、5、7。如果 t 包含其他质因子（如 11、13 等），则直接返回 "-1"。• 这一步通过将 t 不断除以 9 到 2 的数字，如

2025-06-02：最小可整除数位乘积Ⅱ。用go语言，给定一个表示正整数的字符串 num 和一个整数 t。

定义：如果一个整数的每一位都不是 0，则称该整数为“无零数字”。

任务要求：找出一个字符串，表示一个整数，满足以下条件：

1. 该整数大于或等于 num。2. 是一个无零数字。3. 该整数所有数位上的数字相乘得到的积可以被 t 整除。

若存在符合条件的整数，返回其字符串表示；若不存在，返回 "-1"。

num 只包含 ['0', '9'] 之间的数字。

num 不包含前导 0 。

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

输出："1488"。

解释：

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

题目来自力扣3348。

1. 检查 t 的质因子：• 首先，检查 t 是否包含大于 7 的质因子。因为数字的每一位只能是 1-9，所以乘积的质因子只能是 2、3、5、7。如果 t 包含其他质因子（如 11、13 等），则直接返回 "-1"。• 这一步通过将 t 不断除以 9 到 2 的数字，如果最终剩余的值大于 1，说明有大于 7 的质因子。2. 检查 num 是否已经满足条件：• 计算 num 的数字乘积是否能被 t 整除。如果能，直接返回 num。• 这里通过从左到右遍历 num 的每一位，逐步计算 t 的剩余部分（leftT）。如果遍历完 num 后 leftT 变为 1，说明 num 的数字乘积已经是 t 的倍数。3. 尝试构造和 num 长度相同的数字：• 从 num 的最高位开始，尝试找到一个比 num 大的数字，其数字乘积能被 t 整除。• 具体方法：• 从右到左找到第一个可以增加的位（即该位的数字可以增加 1 而不超过 9）。• 对于每个可能的增加位，尝试构造剩余的数字，使得整个数字的数字乘积能被 t 整除。• 构造剩余数字时，从大到小（9 到 1）选择数字，尽可能多地分解 t 的剩余部分。4. 构造比 num 更长的数字：• 如果无法找到和 num 长度相同的数字，则构造一个比 num 长的最小数字。• 将 t 分解为 9 到 2 的数字的乘积，然后按从小到大的顺序排列这些数字（因为我们需要最小的数字）。• 如果分解后的数字位数不足，补 1（因为 1 不影响乘积）。• 时间复杂度：• 检查 t 的质因子：O(1)，因为最多除以 9 到 2 的数字。• 遍历 num 计算 leftT：O(n)，其中 n 是 num 的长度。• 尝试构造相同长度的数字：最坏情况下需要遍历 num 的每一位，并对每一位尝试 9 种可能，因此是 O(n * 9 * n) = O(n^2)。• 构造更长数字：O(log t)，因为需要分解 t 为数字的乘积。• 总体时间复杂度：O(n^2 + log t)。对于大 n（如 2e5），这可能会很慢。• 空间复杂度：• 存储 leftT 数组：O(n)。• 构造结果字符串：O(n) 或 O(log t)。• 总体空间复杂度：O(n)。package mainimport ( "fmt" "slices")func smallestnumber(num string, t int64)string { tmp := int(t) for i := 9; i > 1; i-- { for tmp%i == 0 { tmp /= i } } if tmp > 1 { // t 包含大于 7 的质因子 return"-1" } n := len(num) leftT := make(int, n+1) leftT[0] = int(t) i0 := n - 1 for i, c := range num { if c == '0' { i0 = i break } leftT[i+1] = leftT[i] / gcd(leftT[i], int(c-'0')) } if leftT[n] == 1 { // num 的数位之积已经是 t 的倍数 return num } // 假设答案和 num 一样长 s := byte(num) for i := i0; i >= 0; i-- { for s[i]++; s[i] i; j-- { for tt%k > 0 { k-- } tt /= k s[j] = '0' + byte(k) } if tt == 1 { returnstring(s) } } } // 答案一定比 num 长 ans := byte{} for i := int64(9); i > 1; i-- { for t%i == 0 { ans = append(ans, '0'+byte(i)) t /= i } } forlen(ans)

# -*-coding:utf-8-*-from math import gcddef smallest_number(num: str, t: int) -> str:tmp = tfor i in range(9, 1, -1):while tmp % i == 0:tmp //= iif tmp > 1: # t 包含大于 7 的质因子return "-1"n = len(num)leftT = [t] + [0] * ni0 = n - 1for i, c in enumerate(num):if c == '0':i0 = ibreakdigit = int(c)leftT[i + 1] = leftT[i] // gcd(leftT[i], digit)if leftT[n] == 1: # num 的数字乘积已经是 t 的倍数return nums = list(num)for i in range(i0, -1, -1):s[i] = chr(ord(s[i]) + 1)while s[i] 1:for i in range(9, 1, -1):while t % i == 0:ans.append(str(i))t //= i# 用 1 补足长度while len(ans)