← 返回题目列表

Codeforces · 1043/F

F. 合而为一

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

Janusz 是一名商人。他拥有一家“Januszex”公司,该公司为青少年制作游戏。 Januszex 的最后一款热门游戏是一款很酷的单人游戏“Make it one”。玩家被给予 $$$n$$$ 整数 $$$a_i$$$ 序列。

允许选择其中的任意子集,得分等于所选元素的最大公约数。目标是采用尽可能少的元素,获得分数 $$$1$$$。现在 Janusz 想知道,对于给定的序列,玩家应该选择多少元素?

输入

第一行仅包含一个整数 $$$n$$$ ($$$1 \le n \le 300\,000$$$) — 序列中整数的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 300\,000$$$)。

输出

如果给定序列中不存在 gcd 等于 $$$1$$$ 的子集,则输出 -1。

否则,输出正好一个整数——gcd等于$$$1$$$的最小子集的大小。

示例

输入 #1

3
10 6 15

输出 #1

3

输入 #2

3
2 4 6

输出 #2

-1

输入 #3

7
30 60 21 42 70 15 30

输出 #3

3

注意

在第一个示例中,选择所有数字的子集给出 $$$1$$$ 的 gcd,并且对于所有较小的子集,gcd 大于 $$$1$$$。

在第二个示例中,对于所有数字子集,gcd 至少为 $$$2$$$。