CF371B.Fox Dividing Cheese
普及-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Two little greedy bears have found two pieces of cheese in the forest of weight a and b grams, correspondingly. The bears are so greedy that they are ready to fight for the larger piece. That's where the fox comes in and starts the dialog: "Little bears, wait a little, I want to make your pieces equal" "Come off it fox, how are you going to do that?", the curious bears asked. "It's easy", said the fox. "If the mass of a certain piece is divisible by two, then I can eat exactly a half of the piece. If the mass of a certain piece is divisible by three, then I can eat exactly two-thirds, and if the mass is divisible by five, then I can eat four-fifths. I'll eat a little here and there and make the pieces equal".
The little bears realize that the fox's proposal contains a catch. But at the same time they realize that they can not make the two pieces equal themselves. So they agreed to her proposal, but on one condition: the fox should make the pieces equal as quickly as possible. Find the minimum number of operations the fox needs to make pieces equal.
两只贪吃的小熊在森林里找到了两块奶酪,重量分别为 a 克和 b 克。小熊们非常贪吃,甚至准备为更大的那块奶酪而争斗。这时狐狸出现了,并开始对话:“小熊们,稍等一下,我想让你们的奶酪块变得一样重。”
“别骗人啦,狐狸!你打算怎么做到呢?” 好奇的小熊问道。
“很简单”,狐狸说,“如果某块奶酪的重量能被 2 整除,我就可以恰好吃掉它的一半;如果能被 3 整除,我就可以恰好吃掉它的三分之二;如果能被 5 整除,我就可以恰好吃掉它的五分之四。我会这里吃一点、那里吃一点,最终让两块奶酪重量相等。”
小熊们意识到狐狸的提议中暗藏玄机。但与此同时,它们也明白自己无法靠自身操作使两块奶酪重量相等。因此,它们同意了狐狸的提议,但附加了一个条件:狐狸必须以最少的操作次数使两块奶酪重量相等。
请找出狐狸使两块奶酪重量相等所需的最少操作次数。
输入格式
The first line contains two space-separated integers a and b (1 ≤ a, b ≤ 109).
第一行包含两个用空格分隔的整数 a 和 b(1 ≤ a, b ≤ 109)。
输出格式
If the fox is lying to the little bears and it is impossible to make the pieces equal, print -1. Otherwise, print the required minimum number of operations. If the pieces of the cheese are initially equal, the required number is 0.
如果狐狸在对小熊们说谎,且无法使奶酪块相等,则输出 -1。否则,输出所需的最少操作次数。如果奶酪块初始时已相等,则所需操作次数为 0。
输入输出样例
输入#1
15 20
输出#1
3
输入#2
14 8
输出#2
-1
输入#3
6 6
输出#3
0
输入解题思路,AI测评打分。不知道怎么写?