Required Length

形式化题目

给定两个整数 $n$ 与初值 $x_0$ ，其中 $x_0$ 的十进制位数少于 $n$ 。允许重复执行下面这一种操作：

从当前整数的十进制表示中任选一个出现过的数位 $d$ ，把当前整数替换为它的 $d$ 倍，即 $x \leftarrow x \cdot d$ 。

要求让当前整数的十进制位数（不含前导零）恰好等于 $n$ ，即让 $10^{n-1} \leqslant x \leqslant 10^{n} - 1$ 。求所需的最少操作次数；若无论怎样操作都达不到 $n$ 位，则判定为不可达。

正解

思路

能乘哪些数位完全由当前整数决定，所以「当前整数」就是完整状态，把它当点、一次乘法当边，边权都是 $1$ ，问题就是无权图最短路。用 BFS 按层扩展，队列里存 (当前整数, 步数)，第一次走到 $n$ 位数时的步数就是最少步数。剪枝只需三条：乘 $0$ 之后永远是 $0$ ，乘 $1$ 不改变整数，这两种数位直接跳过；每一步都乘 $\geqslant 2$ ，位数只增不减，所以位数超过 $n$ 的后继直接丢掉。同一个整数能经不同顺序乘出来，用 vis 去重，只展开第一次到达即可，BFS 首次到达即最短。状态数也有上界：乘数只含质因子 $2,3,5,7$ ，可达状态都是 $x_0 \cdot 2^a3^b5^c7^d$ ， $n = 19$ 时这样的数不到 $10^5$ 个，搜索不会爆炸。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53import sys
from collections import defaultdict, deque

## 队列元素：当前整数，已经用掉的步数
type Item = tuple[int,int]


# 返回 n 的十进制位数（不含前导零）
def num_len(n):
    return len(str(n))


# 逐位取出 n 的十进制数位：37 -> 7, 3
def num_iter(n):
    while n :
        yield n % 10
        n //= 10



def solve(data):
    n = next(data)      # 目标位数
    num = next(data)    # 初值 x
    q= deque()          # BFS 队列，按层扩展
    q.append((num,0))   # 初值入队，步数为 0
    vis = defaultdict(bool)  # 访问集合：记录已入队过的整数，防止重复展开
    ans = -1;           # 默认无解，输出 -1

    while q:
        cur,step = q.popleft()   # 队头出队：当前整数与已用步数
        # print(cur,step)
        for i in num_iter(cur):  # 枚举 cur 出现过的每一个数位
            if i ==0 or i == 1 : # 剪枝：乘 0 归零卡死，乘 1 不改变整数
                continue
            nxt = cur * i        # 一步操作：乘上数位 i
            # print(f"nxt({nxt}) = {cur} * {i}")
            if num_len(nxt) > n: # 剪枝：位数已超过 n，之后回不来
                continue
            if num_len(nxt)  == n:   # 首次命中 n 位，BFS 保证步数最少
                ans = step + 1
                print(ans)
                return
            if vis[nxt] == False:    # 去重：只展开第一次到达的状态
                vis[nxt] = True
                q.append((nxt,step+1))
    print(ans)                       # 队列耗尽仍未命中，无解
    
    


if __name__ == "__main__":
    data = iter(map(int, sys.stdin.buffer.read().split()))  # 顺序读入两个整数
    solve(data)

复杂度

设 $S$ 为实际访问的状态数。每个状态要拆出至多 $n$ 位并做常数次乘法，单状态开销 $O(n)$ 。

时间复杂度： $O(S \cdot n)$ ， $n = 19$ 时 $S$ 的量级约 $10^4$ 。
空间复杂度： $O(S)$ ，队列与访问集合各存 $S$ 个整数。

总结

「当前整数」就是完整状态，问题化为无权图最短路，BFS 分层求解，首次碰到 $n$ 位数即答案。
数位 $0$ 会卡死在 $0$ ，数位 $1$ 是空操作，位数超过 $n$ 回不来，这三类分支直接剪掉。
用 vis 去重后每个状态只展开一次；乘数只含质因子 $2,3,5,7$ ，状态总数可控。

目录

形式化题目

正解

思路

代码

复杂度

总结