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.

两只贪吃的小熊在森林里找到了两块奶酪,重量分别为 aa 克和 bb 克。小熊们非常贪吃,甚至准备为更大的那块奶酪而争斗。这时狐狸出现了,并开始对话:“小熊们,稍等一下,我想让你们的奶酪块变得一样重。”
“别骗人啦,狐狸!你打算怎么做到呢?” 好奇的小熊问道。
“很简单”,狐狸说,“如果某块奶酪的重量能被 2 整除,我就可以恰好吃掉它的一半;如果能被 3 整除,我就可以恰好吃掉它的三分之二;如果能被 5 整除,我就可以恰好吃掉它的五分之四。我会这里吃一点、那里吃一点,最终让两块奶酪重量相等。”

小熊们意识到狐狸的提议中暗藏玄机。但与此同时,它们也明白自己无法靠自身操作使两块奶酪重量相等。因此,它们同意了狐狸的提议,但附加了一个条件:狐狸必须以最少的操作次数使两块奶酪重量相等。
请找出狐狸使两块奶酪重量相等所需的最少操作次数。

输入格式

The first line contains two space-separated integers a and b (1 ≤ a, b ≤ 109).

第一行包含两个用空格分隔的整数 aa 和 bb(1 ≤ a, b ≤ 1091 ≤ a, b ≤ 10^9)。

输出格式

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测评打分。不知道怎么写?

首页