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$

输出格式

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

输入输出样例 #1

输入 #1

3
6 9 12

输出 #1

2

输入输出样例 #2

输入 #2

4
8 2 12 6

输出 #2

1

输入输出样例 #3

输入 #3

7
30 28 33 49 27 37 48

输出 #3

7

说明/提示

限制条件

• $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 翻译