CF371B 题解

liangbowen · 2022-06-26 11:15:35 · 题解

前言

题目传送门！

更好的阅读体验？

这题显然没有蓝的难度。

其他题解代码不好看，而且没有讲清楚，那我补一发吧。

题目简述

有两个数 a，b，每次操作可以给 a 或 b 除以 2，3，5。

问最少操作数使得 a = b。无解输出 -1。

思路

设最后，两数都需要等于 x。

即，x 满足 x \mid a, b。

想要得到最少操作数，则 x 要尽可能大。

你想到了什么？

对，x 取 a 和 b 的最大公因数即可！

我们可以令 a' = a \div x，b' = b \div x。

所以，答案即为 a' 与 b' 的因数 2，3，5 的总数。

需要注意，如果 a' 或 b' 不只有这三个因数，说明没法吃完。输出 -1 即可。

代码

我们可以利用函数，来是码风美观。

#include <cstdio>
#include <iostream>
using namespace std;
int gcd(int x, int y)
{
    if (y == 0) return x;
    return gcd(y, x%y);
}
int cnt;
void play(int &x, int k)
//将 x 的所有因数 k 约掉。 
//x 前面的 & 符号可以使程序更改 x 的值。
//如果不加，x 就默认不改变。 
{
    while (x != 0 && x % k == 0) x /= k, cnt++;
}
void X()
{
    printf("-1");
    exit(0);
    //怎么在主函数外结束程序？ 
    //使用 exit(0) 而非 return 0 即可。 
}
int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    int GCD = gcd(a, b);
    a /= GCD, b /= GCD;

    play(a, 2), play(a, 3), play(a, 5);
    if (a != 1) X();

    play(b, 2), play(b, 3), play(b, 5);
    if (b != 1) X();

    printf("%d", cnt);
    return 0;
}

希望能帮助到大家！