c++编程大师精英赛-魔法

2023-12-31 12:39:25

魔法

暂无标签

?题目统计?全部提交

时间限制:C/C++ 1000MS,其他语言 2000MS
内存限制:C/C++ 256MB,其他语言 512MB
难度:简单
出题人:admin

描述

给出两个数 n,m(1≤n≤m≤5*108)
询问能否通过将n 乘 2 和将 n 乘 3 两种操作使 n 变为 m ,如果可行,输出最小操作次数,如果不可行,输出 ?1

输入描述

只有一行,输入包含两个正整数n,m(1≤n≤m≤5*108)

输出描述

输出从n到m的操作次数,如果无法做到则输出-1

用例输入 1?

120 51840

用例输出 1?

7

用例输入 2?

42 42

用例输出 2?

0

用例输入 3?

48 72

用例输出 3?

-1

提示


思路:

我们直接进入正题

首先,int x=m/n

我们来思考一下,如果经过操作,n能变成m,那是不是说明,x是个正整数?

所以,如果m/n!=0,那么输出-1,return 0;

如果m==n那么输出0,return 0;

然后,我们思考一下,既然是通过操作,让n变成m,那x就是n乘了多少倍,那n是不是一定能被2或3整除?

如果n%2!=0||n%3!=0,那么输出-1,return 0;

如果能被整除,那我们就一直x/=2,直到x不能整除2为止,那现在x就是3的倍数,一直除以3就好了


代码:

#include<bits/stdc++.h>
using namespace std;
int main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0);cout.tie(0);
	long long n,m;
	cin>>n>>m;//读入
	if(m%n!=0){
		cout<<-1;return 0;
	}
	if(m==n){
		cout<<0;return 0;
	}
	long long x=m/n,cnt=0;
	if(x%2==0||x%3==0){//如果能整除再计算
		while(x%2==0){//一直除2
			x/=2;cnt++;//除2,执行次数++
		}
		while(x%3==0){
			x/=3;//除3
			cnt++;//执行次数++
		}
	}
	cout<<cnt;//输出执行次数
	return 0;
}

文章来源:https://blog.csdn.net/ptyz306/article/details/135314416
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。