数学家猫猫

T4 数学家猫猫

题面描述

猫猫最近在学习数学，它在黑板上写下了 $N$ 个正整数：$A\_1, A\_2, \dots, A\_N$。为了训练自己的数学思维，它开始进行一项操作游戏。

这个游戏的规则如下：猫猫每次选择黑板上任意两个数，把它们擦掉，并写下它们的 $\gcd$（最大公约数）或者 $\min$（较小值）。这个过程一共重复 $N - 1$ 次，直到黑板上只剩下一个数。

猫猫很好奇，在所有可能的操作顺序以及选择 $\gcd$ 或 $\min$ 的情况下，最后可能留下多少种不同的整数结果？

请你帮助猫猫计算留下的不同整数结果数量。

输入格式

N
A_1 A_2 ... A_N

• 第一行包含一个整数 $N$，表示初始在黑板上的数字个数。
• 第二行包含 $N$ 个整数 $A\_i$，表示这些数字的初始值。

输出格式

输出一个整数，表示最后剩下的数字可能的不同取值个数。

样例

样例 1 输入

3
6 9 12

样例 1 输出

2

样例 1 解释

可能的最终结果有两种：$3$ 和 $6$。例如：

• 操作顺序一：$9$ 和 $12$ 得到 $\gcd(9,12)=3$，再用 $6$ 和 $3$ 得到 $\min(6,3)=3$。
• 操作顺序二：$6$ 和 $12$ 得到 $\gcd(6,12)=6$，再用 $6$ 和 $9$ 得到 $\min(6,9)=6$。

样例 2 输入

7
30 28 33 49 27 37 48

样例 2 输出

7

样例 2 解释

最终可能剩下的数字包括：$1$，$2$，$3$，$4$，$6$，$7$ 和 $27$，共 $7$ 种结果。

样例 3 输入

4
8 2 12 6

样例 3 输出

1

数据范围

• $2 \leq N \leq 2000$
• $1 \leq A\_i \leq 10^9$