ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#6218
サブタスク

달력 1s 1024MB

問題

정올이는 이상한 행성에서 깨어났다. 이 행성에는 N개의 월이 있으며, 각각의 월은 a_1,…,a_N일을 가지고 있다. 게다가 이 행성에는 L일로 이루어진 주가 있다. L은 양의 정수다. 흥미롭게도 정올이는 다음과 같은 사실을 알고 있다:

  • 올바른 L에 대해, 각 월은 최소한 4주(4⋅L일)이다.

  • 올바른 L에 대해, a_i\ mod\ L의 서로 다른 값은 최대 3개다.

불행히도 정올이는 L이 무엇인지 잊어버렸다! 정올이를 도와 가능한 모든 L의 합을 출력하는 프로그램을 작성하시오.

정수의 크기가 커서 64비트 정수 데이터 타입(예: C/C++의 "long long")을 사용해야 할 수도 있다.


入力

첫 번째 줄에 단일 정수 N이 주어진다. (1≤N≤10,000)

두 번째 줄에 N개의 공백으로 구분된 정수 a_1,…,a_N이 주어진다. (1≤a_i≤4⋅10^9, 모든 a_i는 정수다)


出力

가능한 L의 모든 값의 합을 출력한다.


部分問題

番号 点数 条件
#130点

1≤a_i≤10^6

#270点

추가 제약 조건 없음


例題 #1

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

L의 가능한 값은 1, 2, 3, 4, 5, 6, 7이다. 예를 들어, L=7은 유효하다. 왜냐하면 각 월은 최소 28일(4⋅7=28) 이상이어야 하고, 각 월은 0, 2, 또는 3 mod 7 중 하나여야 하기 때문이다.


例題 #2

4
31 35 28 29
23

L의 가능한 값은 1, 2, 3, 4, 6, 7이다. 예를 들어, L=6은 유효하다. 왜냐하면 각 월은 최소 24일(4⋅6=24) 이상이어야 하고, 각 월은 1, 4, 또는 5 mod 6 중 하나여야 하기 때문이다.



出典

USACO 2024 January Silver

ログインしないとコードを書けません。