← 返回题目列表

Codeforces · 1034/A

A. 放大 GCD

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

F 先生有 $$$n$$$ 个正整数,$$$a_1, a_2, \ldots, a_n$$$。

他认为这些整数的最大公约数太小。所以他想通过去掉一些整数来扩大它。

但这道题对他来说太简单了,所以他不想自己做。如果你帮助他,他会给你一些分数作为奖励。

你的任务是计算需要删除的最小整数数,以使剩余整数的最大公约数大于所有整数的最大公约数。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$) — F 先生拥有的整数个数。

第二行包含 $$$n$$$ 整数,$$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 1.5 \cdot 10^7$$$)。

输出

打印一个整数 - 您需要删除的最小整数数,以便剩余整数的最大公约数大于所有整数的最大公约数。

您不应删除所有整数。

如果没有解决方案,则打印“-1”(不带引号)。

示例

输入 #1

3
1 2 4

输出 #1

1

输入 #2

4
6 9 15 30

输出 #2

2

输入 #3

3
1 1 1

输出 #3

-1

注意

在第一个示例中,最大公约数开头为 $$$1$$$。您可以删除$$$1$$$,以便最大公约数放大为$$$2$$$。答案是$$$1$$$。

在第二个示例中,最大公约数开头为 $$$3$$$。您可以删除 $$$6$$$ 和 $$$9$$$,以便将最大公约数放大为 $$$15$$$。没有一种解决方案只能删除一个整数。所以答案是$$$2$$$。

在第三个例子中,没有办法放大最大公约数。所以答案是$$$-1$$$。