#F. [USACO24Jan Silver] Cowlendar

    传统题 2000ms 256MiB

[USACO24Jan Silver] Cowlendar

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目来源:2024 年 USACO 银组一月月赛 T3。题目翻译来自洛谷。

题目描述

Bessie 在一个陌生的星球上醒来。这个星球上有 NN1N1041\le N\le 10^4)个月,分别有 a1,,aNa_1,\ldots,a_N 天(1ai41091\le a_i\le 4\cdot 10^9,所有 aia_i 均为整数)。此外,这个星球上还存在周,一周为 LL 天,其中 LL 是一个正整数。有趣的是,Bessie 知道以下事情:

  • 对于正确的 LL,每个月至少有 44 周。
  • 对于正确的 LLaimodLa_i\bmod L 至多有 33 个不同值。

不幸的是,Bessie 忘记了 LL 是多少!请通过输出 LL 的所有可能值之和来帮助她。

注意这个问题涉及到的整数可能需要使用 64 位整数型(例如,C/C++ 中的 "long long")。

输入格式

输入的第一行包含一个整数 NN。第二行包含 NN 个空格分隔的整数 a1,,aNa_1,\ldots,a_N

输出格式

输出一个整数,为 LL 的所有可能值之和。

样例 #1

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

样例 #2

4
31 35 28 29
23

提示

样例解释 1

LL 的可能值为 11223344556677。例如,L=7L=7 是合法的,因为每个月的至少有 47=284\cdot 7=28 天,且每个月的天数模 77 的余数均为 002233

样例解释 2

LL 的可能值为 112233446677。例如,L=6L=6 是合法的,因为每个月的至少有 46=244\cdot 6=24 天,且每个月的天数模 66 的余数均为 114455

测试点性质

  • 测试点 343-41ai1061\le a_i\le 10^6
  • 测试点 5145-14:没有额外限制。

usaco20242月

未认领
状态
已结束
题目
6
开始时间
2024-2-21 0:00
截止时间
2024-3-29 23:59
可延期
24 小时