← 返回题目列表

Codeforces · 1681/D

D. 所需长度

中文机器翻译题面 查看原题

给你两个整数,$$$n$$$ 和 $$$x$$$。您可以使用整数 $$$x$$$ 执行多个操作。

您执行的每个操作如下:选择 $$$x$$$ 的十进制表示中至少出现一次的任何数字 $$$y$$$,并将 $$$x$$$ 替换为 $$$x \cdot y$$$。

您想要使$$$x$$$(不带前导零)的十进制表示形式的长度等于$$$n$$$。执行此操作所需的最少操作次数是多少?

输入

输入的唯一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$2 \le n \le 19$$$; $$$1 \le x < 10^{n-1}$$$)。

输出

打印一个整数 — 使 $$$x$$$(不带前导零)的十进制表示形式的长度等于 $$$n$$$ 所需的最少操作数,如果不可能,则打印 $$$-1$$$。

示例

输入 #1

2 1

输出 #1

-1

输入 #2

3 2

输出 #2

4

输入 #3

13 42

输出 #3

12

注意

在第二个示例中,以下操作序列实现了目标:

1. 将 $$$x$$$ 乘以 $$$2$$$,因此 $$$x = 2 \cdot 2 = 4$$$;
2. 将 $$$x$$$ 乘以 $$$4$$$,因此 $$$x = 4 \cdot 4 = 16$$$;
3. 将 $$$x$$$ 乘以 $$$6$$$,因此 $$$x = 16 \cdot 6 = 96$$$;
4. 将 $$$x$$$ 乘以 $$$9$$$,因此 $$$x = 96 \cdot 9 = 864$$$。