No.141 Magical Girl Koba
koba-e964Problem Statement
Koba, a magical girl, has learned magic that changes numbers. Koba can use the following two types of magic:
(1) Add $1$ to a number $a$, changing it to $a+1$.
(2) When a number $a$ is not $0$, change $a$ to its reciprocal $1/a$.
Starting from the number $1$ and repeatedly changing it with magic, output the minimum number of magic uses required to reach the given number $M/N$.
If $M/N$ cannot be obtained no matter how $1$ is changed, output $-1$.
$M$ and $N$ are not necessarily coprime; if they are not coprime, it suffices to change the number into the reduced fraction of $M/N$.
For example, if $M = 4, N = 6$, output the minimum number of uses required to change it into 2/3.
Input
The input is given in the following format.M N
Here, $M,N$ are integers satisfying $1 \le M,N \le 10^9$.
Output
Output the minimum number of magic uses required to change $1$ into $M/N$. If $M/N$ cannot be reached regardless of the order in which magic is used, output $-1$. Print a newline at the end.
Sample
Sample 1
Input
2 3
Output
4
Using magic in the order (1),(2),(1),(2) gives 1 → 2 → 1/2 → 3/2 → 2/3, which yields 2/3. There is no way to obtain 2/3 with 3 or fewer uses of magic, so this is the minimum.
Sample 2
Input
10 7
Output
7
Using magic in the order (1),(1),(2),(1),(1),(2),(1) gives 1 → 2 → 3 → 1/3 → 4/3 → 7/3 → 3/7 → 10/7, which yields 10/7.
Sample 3
Input
1000000000 999999999
Output
1000000000
Sample 4
Input
4 6
Output
4
$M, N$ are not necessarily coprime.
Note
Among the test cases, those whose file names begin with "testcase-small-" satisfy $1 \le M,N \le 300$.提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。