CF371B 题解

前言

题目传送门！

更好的阅读体验？

这题显然没有蓝的难度。

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

题目简述

有两个数 \(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;
}

希望能帮助到大家！

首发：2022-06-26 11:15:35