Cowlendar

题目描述

Bessie 在一颗奇怪的星球上醒来。在这个星球上有 $N$（$1\le N\le 10^4$）个月份，分别有 $a_1, \ldots, a_N$ 天（$1\leq a_i \leq 4 \cdot 10^9$，所有 $a_i$ 均为整数）。此外，这个星球上还有“周”，每周有 $L$ 天，其中 $L$ 为正整数。有趣的是，Bessie 知道如下信息： 对于正确的 $L$，每个月至少有 $4$ 周长。 对于正确的 $L$，$a_i\bmod L$ 的不同取值最多只有 $3$ 种。 不幸的是，Bessie 忘记了 $L$ 是多少！请你输出所有可能的 $L$ 的值之和来帮助她。 注意：本题中涉及的整数可能很大，可能需要使用 64 位整数数据类型（例如 C/C++ 中的 "long long"）。

输入格式

第一行包含一个整数 $N$。 第二行包含 $N$ 个用空格分隔的整数 $a_1, \ldots, a_N$。

输出格式

输出一个整数，表示所有可能的 $L$ 的值之和。

12
31 28 31 30 31 30 31 31 30 31 30 31

28

4
31 35 28 29

23

提示

可能的 $L$ 值为 1, 2, 3, 4, 5, 6, 和 7。例如，$L=7$ 是合法的，因为每个月的长度至少为 $4 \cdot 7 = 28$ 天，并且每个月对 7 取模后为 0、2 或 3。 可能的 $L$ 值为 1, 2, 3, 4, 6, 和 7。例如，$L=6$ 是合法的，因为每个月的长度至少为 $4 \cdot 6 = 24$ 天，并且每个月对 6 取模后为 1、4 或 5。 SCORING: Inputs 3-4: $1 \leq a_i \leq 10^6$ Inputs 5-14: 无额外限制 题目作者：Brandon Wang

标签: USACO|2024|Silver

来源

USACO|2024|Silver