← 返回题目列表

Codeforces · 1141/A

A. 游戏 23

中文机器翻译题面 查看原题

Polycarp 玩“游戏 23”。最初他有一个数字$$$n$$$,他的目标是将其转换为$$$m$$$。他可以一步将 $$$n$$$ 乘以 $$$2$$$ 或将 $$$n$$$ 乘以 $$$3$$$。他可以执行任意数量的动作。

打印将 $$$n$$$ 转换为 $$$m$$$ 所需的移动次数。如果不可能,则打印 -1。

很容易证明,任何将 $$$n$$$ 转换为 $$$m$$$ 的方法都包含相同的移动次数(即移动次数不取决于转换方式)。

输入

输入的唯一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le m \le 5\cdot10^8$$$)。

输出

打印将 $$$n$$$ 转换为 $$$m$$$ 的移动次数,如果没有解决方案,则打印 -1。

示例

输入 #1

120 51840

输出 #1

7

输入 #2

42 42

输出 #2

0

输入 #3

48 72

输出 #3

-1

注意

在第一个示例中,可能的移动顺序为: $$$120 \rightarrow 240 \rightarrow 720 \rightarrow 1440 \rightarrow 4320 \rightarrow 12960 \rightarrow 25920 \rightarrow 51840。$$$ 总共有 $$$7$$$ 步。

在第二个示例中,不需要移动。因此,答案是$$$0$$$。

在第三个示例中,不可能将 $$$48$$$ 转换为 $$$72$$$。