GCD 或最小值

题目描述

黑板上写着 $N$ 个整数 $A_1, A_2, A_3, \dots, A_N$。

你要进行以下操作 $N - 1$ 次：

• 选择黑板上的 $2$ 个数并擦掉。设擦掉的数为 $x$ 和 $y$，将 $\gcd(x, y)$ 和 $\min(x, y)$ 中的某一个写在黑板上

在 $N - 1$ 次操作结束后，黑板上只剩一个整数。求这个整数可能有多少种取值？

输入格式

输入按以下格式从标准输入给出：

$N$
$A_1$ $A_2$ $A_3$ $\dots$ $A_N$

输出格式

输出黑板上可能剩下的整数的个数。

样例

3
6 9 12

2

$3$ 和 $6$ 是最后可能留在黑板上的整数。

例如，通过以下操作可以留下 $3$：

• 选择 $9$ 和 $12$ 并从黑板上擦掉，写上 $\gcd(9, 12) = 3$
• 选择 $6$ 和 $3$ 并从黑板上擦掉，写上 $\min(6, 3) = 3$

另外，通过以下操作可以留下 $6$：

• 选择 $6$ 和 $12$ 并从黑板上擦掉，写上 $\gcd(6, 12) = 6$
• 选择 $6$ 和 $9$ 并从黑板上擦掉，写上 $\min(6, 9) = 6$

4
8 2 12 6

1

$2$ 是唯一可能留在黑板上的数。

7
30 28 33 49 27 37 48

7

$1, 2, 3, 4, 6, 7, 27$ 是最后可能留在黑板上的整数。

数据范围

• $2 \le N \le 2000$
• $1 \le A_i \le 10^9$
• 输入均为整数