레이팅 미적용베시가 낯선 행성에서 눈을 떴다. 이 행성에는 \(N\) (\(1\le N\le 10^4\))개의 달이 있고, 각 달은 각각 \(a_1, \ldots, a_N\)일로 이루어져 있다 (\(1\leq a_i \leq 4 \cdot 10^9\), 모든 \(a_i\)는 정수). 또한 이 행성에는 주(week)라는 개념이 있는데, 한 주는 \(L\)일이고 \(L\)은 양의 정수이다. 흥미롭게도 베시는 다음을 알고 있다.
- 올바른 \(L\)에 대해, 각 달은 적어도 \(4\)주 이상이다.
- 올바른 \(L\)에 대해, \(a_i\bmod L\)의 서로 다른 값은 최대 \(3\)개이다.
안타깝게도 베시는 \(L\)이 무엇인지 잊어버렸다! 가능한 모든 \(L\) 값의 합을 출력하여 베시를 도와주자.
이 문제에서 다루는 정수가 매우 클 수 있으므로 64비트 정수 자료형(예: C/C++의 "long long")이 필요할 수 있음에 유의하라.
출제: Brandon Wang
배점
- 입력 3-4: \(1 \leq a_i \leq 10^6\)
- 입력 5-14: 추가 제약 없음
출제: Brandon Wang
첫째 줄에 정수 \(N\)이 주어진다. 둘째 줄에 공백으로 구분된 \(N\)개의 정수 \(a_1, \ldots, a_N\)이 주어진다.
가능한 모든 \(L\) 값의 합을 나타내는 정수 하나를 출력한다.
12
31 28 31 30 31 30 31 31 30 31 30 3128The 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.
4
31 35 28 2923The 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.
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > January > Silver