← 返回题目列表

AtCoder · abc276_d

G. 除以 2 或 3

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

分数: 400 点

问题陈述

给定一个正整数序列: A=(a_1,a_2,\ldots,a_N).
您可以选择并执行以下操作之一任意次数(可能为零)。

  • 选择一个整数 i 这样 1 \leq i \leq N 和 a_i 是的倍数 2,并替换 a_i 与 \frac{a_i}{2}.
  • 选择一个整数 i 这样 1 \leq i \leq N 和 a_i 是的倍数 3,并替换 a_i 与 \frac{a_i}{3}.

你的目标是 A 满足 a_1=a_2=\ldots=a_N.
找出实现目标所需执行操作的最少总次数。如果无法实现目标,则打印 -1 。

约束

  • 2 \leq N \leq 1000
  • 1 \leq a_i \leq 10^9
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
a_1 a_2 \ldots a_N

输出

打印答案。


示例输入 1

3
1 4 3

示例输出 1

3

这是通过三个操作来实现目标的方法,这是最少需要的。

  • 选择一个整数 i=2 这样 a_i 是的倍数 2,并替换 a_2 与 \frac{a_2}{2}. A 变为 分别为 (1,2,3).
  • 选择一个整数 i=2 这样 a_i 是的倍数 2,并替换 a_2 与 \frac{a_2}{2}. A 变为 分别为 (1,1,3).
  • 选择一个整数 i=3 这样 a_i 是的倍数 3,并替换 a_3 与 \frac{a_3}{3}. A 变为 分别为 (1,1,1).

示例输入 2

3
2 7 6

示例输出 2

-1

没有办法达到这个目标。


示例输入 3

6
1 1 1 1 1 1

示例输出 3

0