AT_abc191_f [ABC191F] 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$

输出作为黑板上最后剩下的整数的可能种数。

## 限制条件 - $2 \leq N \leq 2000$ - $1 \leq A_i \leq 10^9$ - 所有输入均为整数 ## 样例解释 1 $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 $2$ 是唯一可能剩下的数。 ## 样例解释 3 $1, 2, 3, 4, 6, 7, 27$ 都是最后可能剩下的整数。 由 ChatGPT 4.1 翻译