1141A.md (1329B)
1 Source: https://codeforces.com/problemset/problem/1141/A 2 3 A. Game 23 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Polycarp plays "Game 23". Initially he has a number $n$ and his goal is to transform it to $m$. In one move, he can multiply $n$ by $2$ or multiply $n$ by $3$. He can perform any number of moves. 22 23 Print the number of moves needed to transform $n$ to $m$. Print -1 if it is impossible to do so. 24 25 It is easy to prove that any way to transform $n$ to $m$ contains the same number of moves (i.e. number of moves doesn't depend on the way of transformation). 26 27 Input 28 29 The only line of the input contains two integers $n$ and $m$ ($1 \le n \le m \le 5\cdot10^8$). 30 31 Output 32 33 Print the number of moves to transform $n$ to $m$, or -1 if there is no solution. 34 35 Examples 36 37 Input 38 39 ``` 40 120 51840 41 ``` 42 43 Output 44 45 ``` 46 7 47 ``` 48 49 Input 50 51 ``` 52 42 42 53 ``` 54 55 Output 56 57 ``` 58 0 59 ``` 60 61 Input 62 63 ``` 64 48 72 65 ``` 66 67 Output 68 69 ``` 70 -1 71 ``` 72 73 Note 74 75 In the first example, the possible sequence of moves is: $120 \rightarrow 240 \rightarrow 720 \rightarrow 1440 \rightarrow 4320 \rightarrow 12960 \rightarrow 25920 \rightarrow 51840.$ The are $7$ steps in total. 76 77 In the second example, no moves are needed. Thus, the answer is $0$. 78 79 In the third example, it is impossible to transform $48$ to $72$.