|
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Polycarp plays "Game 23". Initially he has a number nn and his goal is to transform it to mm. In one move, he can multiply nn by 22 or multiply nn by 33. He can perform any number of moves.
Print the number of moves needed to transform nn to mm. Print -1 if it is impossible to do so.
It is easy to prove that any way to transform nn to mm contains the same number of moves (i.e. number of moves doesn't depend on the way of transformation).
Input
The only line of the input contains two integers nn and mm (1≤n≤m≤51081≤n≤m≤5108).
Output
Print the number of moves to transform nn to mm, or -1 if there is no solution.
Examples
input
Copy
120 51840
output
Copy
7
input
Copy
42 42
output
Copy
0
input
Copy
48 72
output
Copy
-1
Note
In the first example, the possible sequence of moves is: 120→240→720→1440→4320→12960→25920→51840.120→240→720→1440→4320→12960→25920→51840. The are 77 steps in total.
In the second example, no moves are needed. Thus, the answer is 00.
In the third example, it is impossible to transform 4848 to 7272.
解题说明：水题，先判断ab能否整除，如果能整除再判断b是3还是2的倍数。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int main()
{
int a, b, c = 0;
scanf("%d %d", &a, &b);
if (b % a)
{
printf("-1\n");
}
else
{
b = b / a;
while (b % 3 == 0)
{
c++;
b = b / 3;
}
while (b % 2 == 0)
{
c++;
b = b / 2;
}
if (b > 1)
{
puts("-1\n");
}
else
{
printf("%d\n", c);
}
}
return 0;
}
| 
转播
