AT_abc276_d [ABC276D] Divide by 2 or 3

题目描述

给定一个正整数序列 $A=(a_1,a_2,\ldots,a_N)$。
你可以重复执行以下两种操作中的任意一种，次数不限（可以为 $0$ 次）：

• 选择一个满足 $1 \leq i \leq N$ 且 $a_i$ 是 $2$ 的倍数的整数 $i$，将 $a_i$ 替换为 $\frac{a_i}{2}$。
• 选择一个满足 $1 \leq i \leq N$ 且 $a_i$ 是 $3$ 的倍数的整数 $i$，将 $a_i$ 替换为 $\frac{a_i}{3}$。

你的目标是使 $A$ 满足 $a_1=a_2=\ldots=a_N$。
请你求出实现目标所需操作次数的最小值。如果无论如何都无法实现目标，请输出 $-1$。

输入格式

输入按以下格式从标准输入读入。

$N$ $a_1$ $a_2$ $\ldots$ $a_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3
1 4 3

输出 #1

3

输入输出样例 #2

输入 #2

3
2 7 6

输出 #2

-1

输入输出样例 #3

输入 #3

6
1 1 1 1 1 1

输出 #3

0

说明/提示

限制条件

• $2 \leq N \leq 1000$
• $1 \leq a_i \leq 10^9$
• 输入均为整数

样例解释 1

可以按如下方式操作，最少 $3$ 次即可达成目标：

• 选择 $a_i$ 是 $2$ 的倍数的 $i=2$，将 $a_2$ 替换为 $\frac{a_2}{2}$，此时 $A=(1,2,3)$。
• 选择 $a_i$ 是 $2$ 的倍数的 $i=2$，将 $a_2$ 替换为 $\frac{a_2}{2}$，此时 $A=(1,1,3)$。
• 选择 $a_i$ 是 $3$ 的倍数的 $i=3$，将 $a_3$ 替换为 $\frac{a_3}{3}$，此时 $A=(1,1,1)$。

样例解释 2

无论如何操作都无法达成目标。

由 ChatGPT 4.1 翻译