F - GCD或者MIN

得分：$600$分

问题描述

在黑板上写了$N$个整数$A_1, A_2, A_3, \dots, A_N$。
您需要进行以下操作$N - 1$次：

• 选择黑板上写着的两个数字并擦去。记$x$和$y$为被擦去的数字。然后，在黑板上写下$\gcd(x, y)$或者$\min(x, y)$。

经过$N - 1$次操作后，黑板上将只剩下一个整数。这个整数有多少可能的取值？

约束

• $2 \le N \le 2000$
• $1 \le A_i \le 10^9$
• 输入值都是整数。

输入

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

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