刀工对决

题目链接：nowcoder 217128

到主站看：https://blog.csdn.net/weixin_43346722/article/details/116243367

题目大意

给你两个数，你可以对它们进行两种操作，除以三或除以五分之三。
问你能否通过这两个操作把它们变成一样的数，如果可以输出最小次数。

思路

这道题我们观察一下两个操作的性质。

第一个操作： 变成

第二个操作： 变成

那你会发现，如果你做两个操作各一次，就是 变成 。

那你会想到，你要让两个数变成一样，那就是可以把它们 GCD 以外的东西都除成 1。
这其实有一点点贪心的感觉，就是你如果把 GCD 的除了，那两边都要除，而且你除不除都是一样，那还不如不除。

那你看到除 会出 ，那你可以先把 GCD 外的 都除完（记得乘 ），然后接着就把 GCD 外的 都除完。
记得第二次除的时候要重新算 GCD，因为你乘了 ，可能刚好另外一边也有多的 ，这个 就不用除了。

然后如果最后 GCD 外还有数，就说明无解，否则就是你前面除的次数。

代码

#include<cstdio>
#define ll long long

using namespace std;

int n;
ll ans, a, b, gcd;

ll GCD(ll x, ll y) {
    if (!y) return x;
    return GCD(y, x % y);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld %lld", &a, &b);

        ll gcd = GCD(a, b);//先除以一次gcd
        a /= gcd;
        b /= gcd;

        while (a % 5 == 0) {//弄五分之三的
            a = a / 5 * 3;
            ans++;
        }
        while (b % 5 == 0) {
            b = b / 5 * 3;
            ans++;
        }

        gcd = GCD(a, b);//再除一次gcd
        a /= gcd;
        b /= gcd;

        while (a % 3 == 0) {//处理三分之一的
            a = a / 3;
            ans++;
        }
        while (b % 3 == 0) {
            b = b / 3;
            ans++;
        }

        if (a != b) {
            printf("-1");
            return 0;
        }
    }

    printf("%lld", ans);

    return 0;
}