Codeforces Round #547 (Div. 3)A. Game 23
A. Game 23
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≤5⋅1081≤n≤m≤5⋅108).
Output
Print the number of moves to transform nn to mm, or -1 if there is no solution.
题意：给定两个数，A,B，求最少变换次数从A到B，变换方式为乘2或者乘3，如果无解输出-1
思路：很直接我们直接计算B/A，如果等1特判一下0，有余数无解
有解的情况：一直除2，边除次数边加，一直除3边除次数边加，直到为1为止
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#include<unordered_set>
#define rg register ll
#define inf 2147483647
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define maxn 200005
const double eps = 1e-8;
using namespace std;
inline ll read()
{
char ch = getchar(); ll s = 0, w = 1;
while (ch < 48 || ch>57) { if (ch == '-')w = -1; ch = getchar(); }
while (ch >= 48 && ch <= 57) { s = (s << 1) + (s << 3) + (ch ^ 48); ch = getchar(); }
return s * w;
}
inline void write(ll x)
{
if (x < 0)putchar('-'), x = -x;
if (x > 9)write(x / 10);
putchar(x % 10 + 48);
}
ll a,b;
int main()
{
a=read(),b=read();
if(b%a)
{
cout<<-1<<endl;
return 0;
}
ll temp=b/a,ans=0;
while(temp%2==0)
{
temp/=2;
ans++;
}
while(temp%3==0)
{
temp/=3;
ans++;
}
if(temp>1)
{
cout<<-1<<endl;
return 0;
}
else cout<<ans<<endl;
return 0;
}腾讯云开发者
