← 返回题目列表

AtCoder · abc191_f

F. GCD 或 MIN

中文机器翻译题面 查看原题

分数: 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 可以保留在黑板上。