[USACO24JAN] Cowlendar S

Luogu

IDLGP10136

Time2000ms

Memory256MB

DifficultyP5

USACO2024数论鸽笼原理

Bessie 在一个陌生的星球上醒来。这个星球上有 $N$（$1\le N\le 10^4$）个月，分别有 $a_1,\ldots,a_N$ 天（$1\le a_i\le 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"）。** ## Input 输入的第一行包含一个整数 $N$。第二行包含 $N$ 个空格分隔的整数 $a_1,\ldots,a_N$。 ## Output 输出一个整数，为 $L$ 的所有可能值之和。 [samples] ## Note ### 样例解释 1 $L$ 的可能值为 $1$，$2$，$3$，$4$，$5$，$6$ 和 $7$。例如，$L=7$ 是合法的，因为每个月的至少有 $4\cdot 7=28$ 天，且每个月的天数模 $7$ 的余数均为 $0$，$2$ 或 $3$。 ### 样例解释 2 $L$ 的可能值为 $1$，$2$，$3$，$4$，$6$ 和 $7$。例如，$L=6$ 是合法的，因为每个月的至少有 $4\cdot 6=24$ 天，且每个月的天数模 $6$ 的余数均为 $1$，$4$ 或 $5$。 ### 测试点性质 - 测试点 $3-4$：$1\le a_i\le 10^6$。 - 测试点 $5-14$：没有额外限制。

Samples

Input #1

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

Output #1

Input #2

4
31 35 28 29

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[USACO24JAN] Cowlendar S",
    "description": {
      "content": "Bessie 在一个陌生的星球上醒来。这个星球上有 $N$（$1\\le N\\le 10^4$）个月，分别有 $a_1,\\ldots,a_N$ 天（$1\\le a_i\\le 4\\cdot 10^9$，所有 $a_i$ 均为整数）。此外，这个星球上还存在周，一周为 $L$ 天，其中 $L$ 是一个正整数。有趣的是，Bessie 知道以下事情： - 对于正确的 $L$，每个月至少有 $4$ 周。 - ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10136"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Bessie 在一个陌生的星球上醒来。这个星球上有 $N$（$1\\le N\\le 10^4$）个月，分别有 $a_1,\\ldots,a_N$ 天（$1\\le a_i\\le 4\\cdot 10^9$，所有 $a_i$ 均为整数）。此外，这个星球上还存在周，一周为 $L$ 天，其中 $L$ 是一个正整数。有趣的是，Bessie 知道以下事情：\n\n- 对于正确的 $L$，每个月至少有 $4$ 周。\n- ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments