102353: [AtCoder]ABC235 D - Multiply and Rotate
Description
Score : $400$ points
Problem Statement
We have a positive integer $a$. Additionally, there is a blackboard with a number written in base $10$.
Let $x$ be the number on the blackboard. Takahashi can do the operations below to change this number.
- Erase $x$ and write $x$ multiplied by $a$, in base $10$.
- See $x$ as a string and move the rightmost digit to the beginning.
This operation can only be done when $x \geq 10$ and $x$ is not divisible by $10$.
For example, when $a = 2, x = 123$, Takahashi can do one of the following.
- Erase $x$ and write $x \times a = 123 \times 2 = 246$.
- See $x$ as a string and move the rightmost digit
3
of123
to the beginning, changing the number from $123$ to $312$.
The number on the blackboard is initially $1$. What is the minimum number of operations needed to change the number on the blackboard to $N$? If there is no way to change the number to $N$, print $-1$.
Constraints
- $2 \leq a \lt 10^6$
- $2 \leq N \lt 10^6$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$a$ $N$
Output
Print the answer.
Sample Input 1
3 72
Sample Output 1
4
We can change the number on the blackboard from $1$ to $72$ in four operations, as follows.
- Do the operation of the first type: $1 \to 3$.
- Do the operation of the first type: $3 \to 9$.
- Do the operation of the first type: $9 \to 27$.
- Do the operation of the second type: $27 \to 72$.
It is impossible to reach $72$ in three or fewer operations, so the answer is $4$.
Sample Input 2
2 5
Sample Output 2
-1
It is impossible to change the number on the blackboard to $5$.
Sample Input 3
2 611
Sample Output 3
12
There is a way to change the number on the blackboard to $611$ in $12$ operations: $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$, which is the minimum possible.
Sample Input 4
2 767090
Sample Output 4
111
Input
题意翻译
给定两个整数a(2≤a<10^6),x和N(2≤N<10^6),你可以对这两个数进行以下操作。 ·把x乘以a ·将x末尾的数字移动到x的开头(该操作只能在x≥10且x不能被10整除时进行) 例如,当a = 2, x = 123时,你可以进行以下操作。 ·将x乘以a,使x变为246 ·将x末尾的数字移动到x的开头,使x变为312。 x的初始值为1,你需要用最少的操作次数使a变为N。输出最少的操作次数,如果无解,请输出-1。Output
分数:400分
问题描述
我们有一个正整数$a$。此外,还有一个用十进制书写数字的黑板。
- 将黑板上的数字$x$擦除,并用十进制写下$x$乘以$a$的结果。
- 将$x$视为一个字符串,将最右边的数字移动到字符串的最前面。
这个操作只能在$x \geq 10$且$x$不被$10$整除时进行。
例如,当$a = 2, x = 123$时,Takahashi可以进行以下操作之一。
- 擦除$x$并写下$x \times a = 123 \times 2 = 246$。
- 将$x$视为一个字符串,并将最右边的数字
3
移动到字符串的最前面,将数字从$123$变为$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$变为$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
有一种方法可以在$12$次操作中将黑板上的数字变为$611$:$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