← 返回题目列表

AtCoder · abc235_d

G. 乘法和旋转

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

分数: 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 作为字符串并移动最右边的数字 3 of 123 到开头,将数字从 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