/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
正の整数 a があります。また、黒板に 1 個の数が 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 を文字列とみなして、
123の末尾の数字である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
以下に説明する操作を行うことで、 黒板に書かれている数を 4 回で 1 から 72 に変化させることができます。
- 1 つ目の操作を行う。黒板に書かれている数は 1 \to 3 に変わる。
- 1 つ目の操作を行う。黒板に書かれている数は 3 \to 9 に変わる。
- 1 つ目の操作を行う。黒板に書かれている数は 9 \to 27 に変わる。
- 2 つ目の操作を行う。黒板に書かれている数は 27 \to 72 に変わる。
3 回以下の操作で 72 に変化させることはできないため、答えは 4 になります。
入力例 2
2 5
出力例 2
-1
どのように操作しても黒板に書かれている数を 5 に変化させることはできません。
入力例 3
2 611
出力例 3
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 と 12 回の操作で黒板に書かれている数を 611 に変化させることができ、これが最小です。
入力例 4
2 767090
出力例 4
111
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
3of123to 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