Polycarp plays "Game 23". Initially he has a number nn and his goal is to transform it to m. In one move, he can multiply n by 22 or multiply n by 33. He can perform any number of moves.
Print the number of moves needed to transform n to m. Print -1 if it is impossible to do so.
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).
Input
The only line of the input contains two integers n and m (1≤n≤m≤5⋅108).
Output
Print the number of moves to transform n to m, or -1 if there is no solution.
Examples
120 51840
7
42 42
0
48 72
-1
Note
In the first example, the possible sequence of moves is: 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 0.
In the third example, it is impossible to transform 48 to 72.
思路：比较尴尬的一道题，偷看题解不下心被抓到（关键是代码啥也没看到，倒霉的一天），比赛完后才发现网上题解代码千篇一律，思路就是先将m%n如果不等于零直接输出 -1，否则继续往下进行让m/n此时m/n的值应该都是由2 或者是 3乘起来组成（其实不然），那么就继续对其%2或者是%3求进行的次数，但是有一个例外情况就是当n=1时，例如n=1，m=5，此时会进入一个死循环，所以应该加一个判断条件就是当n%2而且n%3都不等于0时候直接令x = -1然后break终止循环。（中间n%6是因为2x3 = 6，实际上可加可不加，所以注释掉）
#include<cstdio>
using namespace std;
int main()
{
long long a,b; a代表题中n，b代表题中m。
while(~scanf("%lld%lld",&a,&b)){
long long x = 0; //x记录执行的次数
if(b%a != 0){
printf("-1\n");
}
else{
b /= a;
while(b != 1){
/*if(b%6 == 0){ // 2x3 = 6，可以直接留下光剩下2或者3的情况，也可以不加，直接忽略
b /= 6;
x += 2;
}*/
if(b%3 == 0){
b /= 3;
x++;
}
else if(b%2 == 0){
b /= 2;
x++;
}
else{ //例如 1 5这种数据在前面b/a的时候无法筛掉，所以在这直接break然后跳出
x = -1;
break;
}
}
printf("%lld\n",x);
}
}
return 0;
}
听说这题可以用搜索，不过我不知道怎么做