Bessie has woken up on a strange planet. In this planet, there are N
(1≤N≤104) months, with a1,…,aN days, respectively (1≤ai≤4⋅109, all ai
are integers). In addition, on the planet, there are also weeks, where each week is L days, with L being a positive integer. Interestingly, Bessie knows the following:
For the correct L, each month is at least 4 weeks long.
For the correct L, there are at most 3 distinct values of ai mod L.
Unfortunately, Bessie has forgotten what L is! Help her by printing the sum of all possible values of L.
Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains a single integer N. The second line contains N
space-separated integers, a1,…,aN.
OUTPUT FORMAT (print output to the terminal / stdout):
A single integer, the sum of all possible values of L.
SAMPLE INPUT:
12
31 28 31 30 31 30 31 31 30 31 30 31
SAMPLE OUTPUT:
28
The possible values of L are 1, 2, 3, 4, 5, 6, and 7. For example, L=7 is valid because each month is at least length 4⋅7=28 days long, and each month is either 0, 2, or 3 mod 7.
SAMPLE INPUT:
4
31 35 28 29
SAMPLE OUTPUT:
23
The possible values of L are 1, 2, 3, 4, 6, and 7. For example, L=6 is valid because each month is at least length 4⋅6=24 days long, and each month is either 1, 4, or 5 mod 6.
SCORING:
Inputs 3-4: 1≤ai≤106
Inputs 5-14: No additional constraints
Problem credits: Brandon Wang
扫码领取USACO试题答案+详细解析
咨询一对一备赛规划
