分数: 600 点
问题陈述
有 N 整数 A_1, A_2, A_3, \dots, A_N 写在黑板上。
您将执行以下操作 N - 1 次:
- 选择黑板上写的两个数字并将其擦掉。让 x 和 y 是被删除的数字。然后,写 黑板上的 \gcd(x, y) or \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
输出
打印黑板上最后剩余数字的可能值的个数。
示例输入 1
3 6 9 12
示例输出 1
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.
示例输入 2
4 8 2 12 6
示例输出 2
1
2 是黑板上唯一可以保留的数字。
示例输入 3
7 30 28 33 49 27 37 48
示例输出 3
7
1, 2, 3, 4, 6, 7,和 27 可以保留在黑板上。