A. Game 23
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
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.
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
inputCopy
120 51840
outputCopy
7
inputCopy
42 42
outputCopy
0
inputCopy
48 72
outputCopy
-1
Note
In the first example, the possible sequence of moves is: 120→240→720→1440→4320→12960→25920→51840. The are 7 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.
值得注意的是
- 超时 单是除会超时，那么应该如何去简化算法呢？
#include<iostream>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
if(m%n==0)
{
int cishu=0;
int k=m/n;
while(k%2==0)
{chishu++;k=k/2;}
while(k%3==0)
{cishu++;k=k/3;}
if(k==1)
{cout<<cishu<<endl;}
else
{cout<<-1<<endl;}
}
else
{cout<<-1<<endl;}
return 0;
}
把2全除尽
把3全除尽
就是这样......
