分数: 400 点
问题陈述
我们有一个正整数 a。另外,还有一块黑板,上面写着数字 10.
让 x 是黑板上的数字。高桥可以通过以下操作来更改此号码。
- 擦除 x 并写 x 乘以 a,在基地 10.
- 参见 x 作为字符串并将最右边的数字移到开头。
此操作只能在以下情况下完成 x \geq 10 和 x 不能被整除 10.
例如,当 a = 2, x = 123,高桥可以执行以下操作之一。
- 擦除 x 并写 x \times a = 123 \times 2 = 246.
- 参见 x 作为字符串并移动最右边的数字
3of123到开头,将数字从 123 to 312.
黑板上的数字最初是 1。将黑板上的数字改为最少需要多少次操作 N?如果没有办法将号码更改为 N,打印 -1.
约束
- 2 \leq a \lt 10^6
- 2 \leq N \lt 10^6
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
a N
输出
打印答案。
示例输入 1
3 72
示例输出 1
4
我们可以将黑板上的数字从 1 to 72 四次操作,如下。
- 进行第一种操作: 1 \to 3.
- 进行第一种操作: 3 \to 9.
- 进行第一种操作: 9 \to 27.
- 进行第二类操作: 27 \to 72.
不可能到达 72 三个或更少的操作,所以答案是 4.
示例输入 2
2 5
示例输出 2
-1
不可能把黑板上的数字改成 5.
示例输入 3
2 611
示例输出 3
12
有一种方法可以将黑板上的数字更改为 611 in 12 操作: 1 \to 2 \to 4 \to 8 \to 16 \to 32 \to 64 \to 46 \to 92 \to 29 \to 58 \to 116 \to 611,这是可能的最小值。
示例输入 4
2 767090
示例输出 4
111