Not Adding

题目描述

给定一个由 $n$ 个互不相同的整数构成的数组 $a_1, a_2, \dots, a_n$。你可以对其进行如下操作：

• 从数组中选择两个元素 $a_i$ 和 $a_j$（$i \ne j$），如果 $\gcd(a_i, a_j)$ 不在数组中，则将 $\gcd(a_i, a_j)$ 添加到数组末尾。这里 $\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数。

注意，每次操作后数组都会发生变化，后续操作均在新数组上进行。

你最多可以对该数组进行多少次上述操作？

输入格式

第一行包含一个整数 $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

样例输出

3

样例 #2

样例输入

3
6 10 15

样例输出

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$。

由 ChatGPT 4.1 翻译