刀工对决

题目描述

为了争夺传说中的厨具永灵刀,特级厨师小当家和七星刀雷恩展开了神前刀工对决。对决总共有nn轮刀工测试,每轮给出两块鲷鱼肉,一块长度为aa,另一块长度为bb,厨师必须把这两份鲷鱼肉切成一样长。

已知小当家总共有两把菜刀,每把作用如下:

钢丝菜刀:若当前鲷鱼肉长度xx为3的倍数,可以切掉三分之二的鲷鱼肉,切掉的部分必须扔掉,即xx 变为图片说明
百穴菜刀:若当前鲷鱼肉长度xx为5的倍数,可以切掉五分之二的鲷鱼肉,切掉的部分必须扔掉,即xx变为 xx

小当家每使用菜刀切一刀鲷鱼肉就要花费1秒,请问小当家完成n轮测试的最短时间是多少。

输入描述:

第一行一个正整数n,n图片说明 图片说明

接下来n行,每行两个正整数a与b,其中a ,b

输出描述:

输出小当家完成n轮测试的最短时间,若小当家无法完成某一轮测试,输出-1。

分析:

需要将鱼切成相同长的,也就是经过图片说明 次将第k组鱼变成两种操作下的最大解。
将其按照3、5因数分解,下面两句解题关键:

  1. 如果分解完3和5剩下的数不相等,那么不能成功,返回-1
  2. 对于因子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;
}