差值卡片

【题目描述】

小林收集了 $n$ 张数字卡片，第 $i$ 张卡片上写着正整数 $a_i$．不同卡片上的数字可以相同．

他可以进行任意多次下面的操作，也可以不操作：

选出两张数字不同的卡片，设上面的数字为 $x$ 和 $y$，再制作一张写着 $|x-y|$ 的新卡片．原来的卡片都会保留，新卡片也可以参与之后的操作．

小林只关心收集到了多少种不同的数字．请你求出，经过操作后，所有卡片上最多能出现多少种不同的正整数．

例如，多张卡片都写着 $6$ 时，数字 $6$ 仍然只算一种．由于只能选择数字不同的卡片，操作不会产生 $0$．

【输入描述】

第一行输入一个整数 $n$，表示初始卡片的数量．

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示初始卡片上的数字．

【输出描述】

输出一个整数，表示最多能出现的不同正整数的数量．

【样例 1】

【样例 1 输入】

2
8 12

【样例 1 输出】

3

【样例 1 解释】

选择写着 $8$ 和 $12$ 的卡片，可以制作一张写着 $4$ 的卡片．此时已有的不同数字为 $4,8,12$．任意两个不同数字的差都已经在其中，不能再得到其他数字，因此答案为 $3$．

【样例 2】

【样例 2 输入】

3
1 5 5

【样例 2 输出】

5

【样例 2 解释】

先用 $5$ 和 $1$ 得到 $4$，再用新得到的 $4$ 和 $1$ 得到 $3$，接着得到 $2$．最终可以收集到 $1,2,3,4,5$．初始的两张 $5$ 只算一种数字．

【样例 3】

【样例 3 输入】

4
21 21 21 21

【样例 3 输出】

1

【样例 3 解释】

没有两张数字不同的卡片，不能进行操作，已有数字也只算一种．

【样例 4】

见选手目录下的 Data/sample4.in 和 Data/sample4.ans．该样例满足所有 $a_i\le 200$．

【样例 5】

见选手目录下的 Data/sample5.in 和 Data/sample5.ans．该样例满足 $a_1=1$．

【样例 6】

见选手目录下的 Data/sample6.in 和 Data/sample6.ans．该样例满足最小的初始数字能整除所有初始数字．

【样例 7】

见选手目录下的 Data/sample7.in 和 Data/sample7.ans．该样例满足 $n\le 2$．

【样例 8】

见选手目录下的 Data/sample8.in 和 Data/sample8.ans．该样例无特殊性质．

【数据规模与约定】

对于所有测试数据，保证 $1\le n\le 2\times 10^5$，$1\le a_i\le 10^9$．

本题共有五个相互独立的子任务．只有通过一个子任务中的全部测试点，才能获得该子任务的分数．

子任务编号	分数	特殊限制
1	20	所有 $a_i\le 200$
2	10	$a_1=1$
3	20	设 $v=\min(a_1,a_2,\ldots,a_n)$，所有 $a_i$ 都是 $v$ 的倍数
4		$n\le 2$
5	30	无特殊限制

【大样例下载链接】

点击下载本题选手目录