#PU1376. USACO 2024 January Contest, Silver — Problem 3. Cowlendar

USACO 2024 January Contest, Silver — Problem 3. Cowlendar

USACO 2024 January Contest, Silver — Problem 3. Cowlendar

题目描述

Bessie has woken up on a strange planet. In this planet, there are NN (1≤N≤1041\le N\le 10^4) months, with a1,…,aNa_1, \ldots, a_N days, respectively (1≤ai≤4⋅1091\leq a_i \leq 4 \cdot 10^9, all aia_i are integers). In addition, on the planet, there are also weeks, where each week is LL days, with LL being a positive integer. Interestingly, Bessie knows the following: For the correct LL, each month is at least 44 weeks long. For the correct LL, there are at most 33 distinct values of ai mod La_i\bmod L. Unfortunately, Bessie has forgotten what LL is! Help her by printing the sum of all possible values of LL.

输入格式

The first line contains a single integer NN. The second line contains NN space-separated integers, a1,…,aNa_1, \ldots, a_N.

输出格式

A single integer, the sum of all possible values of LL.

数据范围

Inputs 3-4: 1≤ai≤1061 \leq a_i \leq 10^6 Inputs 5-14: No additional Problem credits: Brandon Wang

样例

样例 1

12
31 28 31 30 31 30 31 31 30 31 30 31
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 \cdot 7 = 28$ days long, and each
month is either 0, 2, or 3 mod 7.

样例 2

4
31 35 28 29
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 \cdot 6 = 24$ days long, and each month
is either 1, 4, or 5 mod 6.

提示

use of 64-bit integer data types (e.g., a "long long" in C/C++).