Responsive image

问题 F: 煜的gcd

问题 F: 煜的gcd

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 49
[提交][状态][讨论版][命题人:]

题目描述

煜有一个长度为 n 正整数数组 a。
可以进行任意次操作，每次操作选择数组 a 的两个元素，其中一个加 1，另一个减 1，要求每次操作后 a 的各元素仍然是正整数。
煜想知道操作结束后，数组的最大公约数可能有多少种不同的值？
数组的最大公约数指，该数组的所有数共有约数中最大的那个数。
例如数组 [20,12,16]，共有的约数有 1,2,4，最大的数是 4，因此 [20,12,16]的最大公约数是4。

输入描述

第一行输入一个整数n。
第二行输入 n 个整数 ai。
1≤n,ai≤2×105

输出描述

输出一个整数

样例输入

3
2 4 8

样例输出

2

提示

如果数组不变，最大公约数是 2。

如果数组变成 [1,5,8]，最大公约数是 1。

总共 2 种不同的值。

[提交][状态]
ACM算法攻关部