GCD or MIN

题目描述

黑板上写着 $N$ 个整数 $A_1, A_2, A_3, \dots, A_N$。
你将执行以下操作 $N - 1$ 次：

从黑板上选择两个数字并将它们擦去。设被擦去的数字为 $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

4
8 2 12 6

1

7
30 28 33 49 27 37 48

7

提示

$2 \le N \le 2000$ $1 \le A_i \le 10^9$ 输入中的所有数值均为整数。最后可能剩下的数是 $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$。
$2$ 是黑板上唯一可能剩下的数字。
$1$, $2$, $3$, $4$, $6$, $7$, 和 $27$ 都可能剩在黑板上。

标签: AtCoder|abc191F

来源

AtCoder|abc191F