← 返回题目列表

Codeforces · 1203/C

C. 公约数

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

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。

你的任务是说出这样的正整数 $$$x$$$ 的数量,使得 $$$x$$$ 可以除以数组中的每个数字。换句话说,你必须找到数组中所有元素的公约数。

例如,如果数组 $$$a$$$ 为 $$$[2, 4, 6, 2, 10]$$$,则 $$$1$$$ 和 $$$2$$$ 将数组中的每个数字相除(因此此测试的答案为 $$$2$$$)。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 4 \cdot 10^5$$$) — $$$a$$$ 中的元素数量。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$),其中 $$$a_i$$$ 是 $$$a$$$ 的第 $$$i$$$ 个元素。

输出

打印一个整数 - 此类正整数 $$$x$$$ 的数量,使得 $$$x$$$ 除以给定数组中的每个数字(换句话说,答案是数组中所有元素的公约数)。

示例

输入 #1

5
1 2 3 4 5

输出 #1

1

输入 #2

6
6 90 12 18 30 18

输出 #2

4