刀工对决

题目描述

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

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

钢丝菜刀：若当前鲷鱼肉长度为3的倍数，可以切掉三分之二的鲷鱼肉，切掉的部分必须扔掉，即 变为
百穴菜刀：若当前鲷鱼肉长度为5的倍数，可以切掉五分之二的鲷鱼肉，切掉的部分必须扔掉，即变为

小当家每使用菜刀切一刀鲷鱼肉就要花费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;
}