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 nby 22 or multiply nby 33. He can perform any number of moves.
- Print the number of moves needed to transform nto m. Print -1 if it is impossible to do so.
- It is easy to prove that any way to transform nto mcontains 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 nand m(1≤n≤m≤5108).
- Output
- Print the number of moves to transform nto m, or -1 if there is no solution.
- Examples
- Input
- 120 51840
- Output
- 7
- Input
- 42 42
- Output
- 0
- Input
- 48 72
- Output
- -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 48to 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;
- }
听说这题可以用搜索, 不过我不知道怎么做
来源: http://www.bubuko.com/infodetail-2997245.html