← 返回题目列表

Codeforces · 1627/D

D. 不添加

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

您有一个数组 $$$a_1, a_2, \dots, a_n$$$ 由 $$$n$$$ 不同的整数组成。您可以对其进行以下操作:

- 从数组 $$$a_i$$$ 和 $$$a_j$$$ ($$$i \ne j$$$) 中选择两个元素,使得 $$$\gcd(a_i, a_j)$$$ 不存在于数组中,并将 $$$\gcd(a_i, a_j)$$$ 添加到数组末尾。这里 $$$\gcd(x, y)$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的最大公约数 (GCD)。

请注意,每次操作后数组都会发生变化,后续操作都会在新数组上执行。

对数组执行操作的最大次数是多少?

输入

第一行由单个整数 $$$n$$$ ($$$2 \le n \le 10^6$$$) 组成。

第二行由 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^6$$$) 组成。所有 $$$a_i$$$ 都是不同的。

输出

输出包含一个整数的单行 — 可以对给定数组执行操作的最大次数。

示例

输入 #1

5
4 20 1 25 30

输出 #1

3

输入 #2

3
6 10 15

输出 #2

4

注意

在第一个示例中,对数组执行最大次数操作的方法之一是:

- 选择 $$$i = 1, j= 5$$$ 并将 $$$\gcd(a_1, a_5) = \gcd(4, 30) = 2$$$ 添加到数组中。
- 选择 $$$i = 2, j= 4$$$ 并将 $$$\gcd(a_2, a_4) = \gcd(20, 25) = 5$$$ 添加到数组中。
- 选择 $$$i = 2, j= 5$$$ 并将 $$$\gcd(a_2, a_5) = \gcd(20, 30) = 10$$$ 添加到数组中。

可以证明,没有办法对原数组执行超过$$$3$$$的操作。

在第二个示例中,可以添加 $$$3$$$,然后添加 $$$1$$$,然后添加 $$$5$$$,最后添加 $$$2$$$。