刀工对决

刀工对决

思路:
关键在于2号刀，砍了一刀之后要除以5然后乘以3，就会有一个3的幂次，每用一次2号刀就会乘以一次3，3的幂次就会加一。
首先找到a,b的最大公约数，a和b都除以gcd(a,b)，然后a，b就互质了，那么一个里面有 3 这个因子，一个里面有 5 这个因子；先将 5 这个因子用2号刀砍，然后看两边是不是都是三的幂次，不是就直接输出-1 + return 0，是的话答案ans加上幂次的差。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define PI acos(-1)
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int, int> pii;
const ll mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int maxn = 1e6 + 7;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define debug freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout);
inline ll read() {//快读
    ll s = 0, w = 1;char ch = getchar();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) {putchar('0');return;}
    char F[40];ll tmp = x > 0 ? x : -x;if (x < 0)putchar('-');int cnt = 0;while (tmp > 0) {F[cnt++] = tmp % 10 + '0';tmp /= 10;}
    while (cnt > 0)putchar(F[--cnt]);}
inline ll gcd(ll x, ll y) {//最大公约数
    return y ? gcd(y, x % y) : x;}
inline ll lcm(ll x, ll y) {//最小公倍数
    return x / gcd(x, y) * y;
}
ll qpow(ll a, ll b) {//快速幂
    ll ans = 1;while (b) {if (b & 1)ans *= a;b >>= 1;a *= a;}
    return ans;}
ll qpow(ll a, ll b, ll mod) {//快速幂取余
    ll ans = 1;while (b) {if (b & 1)(ans *= a) %= mod;b >>= 1;(a *= a) %= mod;}
    return ans % mod;}
inline int lowbit(int x) {
    return x & (-x);
}
/*
int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};
*/
int ans;
int main()
{
    int n;
    cin >> n;
    while(n--) {
        int a, b;
        cin >> a >> b;
        int tmp = __gcd(a, b);
        a /= tmp, b /= tmp;
        int cnta = 0, cntb = 0;
        while(a % 5 == 0) cnta ++, a /= 5, a *= 3;
        while(b % 5 == 0) cntb ++, b /= 5, b *= 3;
        int s1 = abs(cnta - cntb);
        cnta = 0, cntb = 0;
        while(a % 3 == 0) cnta ++, a /= 3;
        while(b % 3 == 0) cntb ++, b /= 3;
        int s2 = abs(cnta - cntb);
        if(a != b) {
            cout << -1 << endl;
            return 0;
        }
        ans += s1 + s2;
    }
    cout << ans << endl;
    return 0;
}