Codeforces Round #547 (Div. 3)A. Game 23

glm233

发布于 2020-09-28 10:33:44

4330

发布于 2020-09-28 10:33:44

文章被收录于专栏：glm的全栈学习之路

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;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019/08/09 ，如有侵权请联系 cloudcommunity@tencent.com 删除

css