刀工对决
题目描述
为了争夺传说中的厨具永灵刀,特级厨师小当家和七星刀雷恩展开了神前刀工对决。对决总共有nn轮刀工测试,每轮给出两块鲷鱼肉,一块长度为aa,另一块长度为bb,厨师必须把这两份鲷鱼肉切成一样长。
已知小当家总共有两把菜刀,每把作用如下:
钢丝菜刀:若当前鲷鱼肉长度为3的倍数,可以切掉三分之二的鲷鱼肉,切掉的部分必须扔掉,即
变为
百穴菜刀:若当前鲷鱼肉长度为5的倍数,可以切掉五分之二的鲷鱼肉,切掉的部分必须扔掉,即
变为
小当家每使用菜刀切一刀鲷鱼肉就要花费1秒,请问小当家完成n轮测试的最短时间是多少。
输入描述:
第一行一个正整数n,n
接下来n行,每行两个正整数a与b,其中a ,b
。
输出描述:
输出小当家完成n轮测试的最短时间,若小当家无法完成某一轮测试,输出-1。
分析:
需要将鱼切成相同长的,也就是经过 次将第k组鱼变成两种操作下的最大解。
将其按照3、5因数分解,下面两句解题关键:
- 如果分解完3和5剩下的数不相等,那么不能成功,返回-1
- 对于因子5,次数小的情况下保留最大解,及两个数的较小数
代码:
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<ctime> #include<cstring> #include<string> #include<queue> #include<set> #include<map> #include<vector> #include<bitset> #include<stack> using namespace std; #define D(x) cout<<#x<<" = "<<x<<" " #define E cout<<endl #define rep(i,s,t) for(int (i)=(s);(i)<=(t);(i)++) #define rep0(i,s,t) for(int i=(s);i<(t);i++) #define rrep(i,t,s) for(int i=(t);i>=(s);i--) typedef long long ll; typedef pair<int,int> pii; const int N=1e5+5; const int INF=0x3f3f3f3f; const double pi=acos(-1.0); int n,ans=0; int ar[5],br[5]; void output(){ // cout<<res; } void solve(){ cin>>n; while(n--){ int a,b; cin>>a>>b; ar[1]=ar[2]=br[1]=br[2]=0; while(a%3==0) a/=3,ar[1]++; while(a%5==0) a/=5,ar[2]++; while(b%3==0) b/=3,br[1]++; while(b%5==0) b/=5,br[2]++; if(a!=b){ ans=-1;break; } if(ar[2]>br[2]) ar[1]+=ar[2]-br[2],ans+=ar[2]-br[2]; else br[1]+=br[2]-ar[2],ans+=br[2]-ar[2]; ans+=abs(ar[1]-br[1]); } cout<<ans<<endl; } int main(){ //freopen("2.in","r",stdin); solve(); output(); return 0; }