← 返回题目列表

Codeforces · 1325/E

E. Ehab 的实数论问题

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

给定一个长度为 $$$n$$$ 的数组 $$$a$$$,它有一个特殊条件:该数组中的每个元素最多有 7 个除数。求该数组乘积的最短非空子序列的长度,其元素是完全平方数。

如果 $$$a$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$b$$$ 获得,则序列 $$$a$$$ 是数组 $$$b$$$ 的子序列。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1$$$、$$$a_2$$$、$$$\ldots$$$、$$$a_{n}$$$ ($$$1 \le a_i \le 10^6$$$) — 数组 $$$a$$$ 的元素。

输出

输出 $$$a$$$ 的乘积的最短非空子序列的长度,其元素是完全平方数。如果有几个最短子序列,则可以找到其中任何一个。如果没有这样的子序列,则打印“-1”。

示例

输入 #1

3
1 4 6

输出 #1

1

输入 #2

4
2 3 6 6

输出 #2

2

输入 #3

3
6 15 10

输出 #3

3

输入#4

4
2 3 5 7

输出#4

-1

注意

在第一个示例中,您可以选择子序列$$$[1]$$$。

在第二个示例中,您可以选择子序列 $$$[6, 6]$$$。

在第三个示例中,您可以选择子序列 $$$[6, 15, 10]$$$。

在第四个样本中,没有这样的子序列。