Kimi LeetCode 3348. 最小可整除数位乘积 II Rust实现

这道题（LeetCode 3348）是难度极高的贪心/构造题。核心思路如下：

1. 质因子分析：数位 1\sim9 的乘积只含质因子 2,3,5,7。若 t 分解后含有其他质因子，直接返回 `"-1"`。
2. 预处理 0：若 `num` 中出现 0，从第一个 0 开始把后面全部变成 1（因为答案必须是无零数字）。
3. 从后往前贪心修改：维护还需要的质因子个数 `diff`。先假设整个 `num` 不变，从末尾开始逐位恢复该位的贡献，然后尝试把当前位增大 1\sim9，再用贪心（优先用 8,9,4,6 等“单位位数贡献质因子最多”的数字）判断剩余后缀能否在剩余位数内凑齐所需质因子。若能，则从低位到高位填入大数、中间补 1，得到最小合法答案。
4. 增加位数：若修改失败，则答案长度必为 n+1。构造满足 t 的最短数字串，前面补 1 至长度 n+1 即可。

参考了力扣中文站的高赞 C++ 解法思路，下面是可直接提交的 Rust 实现：

```rust
impl Solution {
pub fn smallest_number(num: String, t: i64) -> String {
let primes: [i64; 4] = [2, 3, 5, 7];
// 优先使用“效率”高的数字（单位位数贡献的质因子多），以最小化所需位数
let ord: [usize; 8] = [8, 9, 4, 6, 2, 3, 5, 7];
// pf[d][i] 表示数字 d 包含第 i 个质因子（2,3,5,7）的个数
let pf: [[i32; 4]; 10] = [
[0, 0, 0, 0],
[0, 0, 0, 0],
[1, 0, 0, 0],
[0, 1, 0, 0],
[2, 0, 0, 0],
[0, 0, 1, 0],
[1, 1, 0, 0],
[0, 0, 0, 1],
[3, 0, 0, 0],
[0, 2, 0, 0],
];

let n = num.len();
let mut num_chars: Vec<char> = num.chars().collect();

// 1. 处理 num 中的 0：第一个 0 及之后全部变成 1
for i in 0..n {
if num_chars[i] > '0' {
continue;
}
for j in i..n {
num_chars[j] = '1';
}
break;
}

// 2. 分解 t，只保留质因子 2,3,5,7
let mut diff = [0i32; 4];
let mut tt = t;
for i in 0..4 {
while tt % primes[i] == 0 {
tt /= primes[i];
diff[i] += 1;
}
}
if tt > 1 {
return "-1".to_string();
}

// 3. 用 num 的各位抵消所需的质因子
for c in &num_chars {
let d = (*c as u8 - b'0') as usize;
for i in 0..4 {
diff[i] -= pf[d][i];
}
}
if diff.iter().all(|&d| d <= 0) {
return num_chars.into_iter().collect();
}

// 4. 从后往前尝试修改某一位
for i in (0..n).rev() {
// 恢复下一位 num[i+1] 的贡献（后缀可自由填充）
if i + 1 < n {
let d = (num_chars[i + 1] as u8 - b'0') as usize;
for j in 0..4 {
diff[j] += pf[d][j];
}
}

let cur = (num_chars[i] as u8 - b'0') as usize;
for d in (cur + 1)..=9 {
let mut buf = diff;
// 恢复当前位原数字的贡献，再减去新数字 d 的贡献
for j in 0..4 {
buf[j] += pf[cur][j];
buf[j] -= pf[d][j];
}

// 贪心：用 ord 中的数字尽可能多地填充，减少所需位数
let mut cnt = [0i32; 10];
for &x in &ord {
let mut res = i32::MAX;
let mut ok = true;
for j in 0..4 {
if pf[x][j] == 0 {
continue;
}
if buf[j] <= 0 {
ok = false;
break;
}
res = res.min(buf[j] / pf[x][j]);
}
if !ok {
continue;
}
let c = if res == i32::MAX { 0 } else { res };
cnt[x] = c;
for j in 0..4 {
buf[j] -= pf[x][j] * c;
}
}

let total: i32 = cnt.iter().sum();
if total > (n - i - 1) as i32 {
continue;
}

// 构造答案：从低位到高位填入大数字，中间补 1
let mut k = n - 1;
for x in (2..=9).rev() {
for _ in 0..cnt[x] {
num_chars[k] = (b'0' + x as u8) as char;
k -= 1;
}
}
while k > i {
num_chars[k] = '1';
k -= 1;
}
num_chars[i] = (b'0' + d as u8) as char;
return num_chars.into_iter().collect();
}
}

// 5. 必须增加位数：构造最短合法串，前面补 1 至长度 n+1
let d0 = (num_chars[0] as u8 - b'0') as usize;
for j in 0..4 {
diff[j] += pf[d0][j];
}

let mut cnt = [0i32; 10];
for x in (2..=9).rev() {
let mut res = i32::MAX;
let mut ok = true;
for j in 0..4 {
if pf[x][j] == 0 {
continue;
}
if diff[j] <= 0 {
ok = false;
break;
}
res = res.min(diff[j] / pf[x][j]);
}
if !ok {
continue;
}
let c = if res == i32::MAX { 0 } else { res };
cnt[x] = c;
for j in 0..4 {
diff[j] -= pf[x][j] * c;
}
}

let mut res_chars = Vec::new();
for x in (2..=9).rev() {
for _ in 0..cnt[x] {
res_chars.push((b'0' + x as u8) as char);
}
}
if res_chars.len() <= n {
let ones = n + 1 - res_chars.len();
for _ in 0..ones {
res_chars.push('1');
}
}
res_chars.reverse();
res_chars.into_iter().collect()
}
}
```

复杂度：O(n \cdot 9 \cdot 8)，其中 n \le 2\times10^5，实际运行近似线性；空间 O(n)。