刀工对决

刀工对决

https://ac.nowcoder.com/acm/contest/11169/B

刀工对决

题目链接: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;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
06-12 18:53
第一次听说还有无水工作!!!又是被刷新三观的一天
Lynn012:666第一次听到,你给他说这里不方便我们加个微信
点赞 评论 收藏
分享
秋盈丶:后续:我在宿舍群里和大学同学分享了这事儿,我好兄弟气不过把他挂到某脉上了,10w+阅读量几百条评论,直接干成精品贴子,爽
点赞 评论 收藏
分享
屌丝逆袭咸鱼计划:心态摆好,man,晚点找早点找到最后都是为了提升自己好进正职,努力提升自己才是最关键的😤难道说现在找不到找的太晚了就炸了可以鸡鸡了吗😤早实习晚实习不都是为了以后多积累,大四学长有的秋招进的也不妨碍有的春招进,人生就这样
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务