Majority Opinion.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types

Bessie se ha despertado en un planeta extraño. En este planeta, hay N meses, con a_1, \ldots ,a_N días, respectivamente (todos los a_i son enteros). En adición, en el planeta, también hay semanas, donde cada semana tiene L días, con L entero positivo. De manera interesante, Bessie sabe lo siguiente:

  • Para el L correcto, cada mes tiene al menos 4 semanas.
  • Para el L correcto, hay a lo más 3 valores distintos de a_i mod L.

Desafortunadamente, Bessie se ha olvidado el valor de L. Ayúdela imprimiendo la suma de todos los valores posibles de L.

Entrada

La primera línea contiene un solo entero N. La segunda línea contiene N enteros separados por espacios, a_1, \ldots ,a_N. Note que los tamaños grandes de los enteros involucrados en este problema podrían requerir el uso de enteros de 64-bits (por ejemplo, un "long long" en C/C++).

Salida

Un solo entero, la suma de todos los valores posibles de L.

Restricciones

  • 1 \leq N \leq 10^4
  • 1 \leq a_i \leq 4 \cdot 10^9

Ejemplo #1 de Entrada

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

Ejemplo #1 de Salida

28

Los valores posibles de L son 1, 2, 3, 4, 5, 6, y 7. Por ejemplo, L=7 es válido debido a que cada mes tiene 4 \cdot 7 = 28 días, y cada mes es 0, 2, o 3 mod 7.

Ejemplo #2 de Entrada

4
31 35 28 29

Ejemplo #2 de Salida

23

Los valores posibles de L son 1, 2, 3, 4, 6, y 7. Por ejemplo, L=6 es válido debido a que cada mes tiene el menos 4 \cdot 6=24 días, y cada mes es o 1, 4, o 5 mod 6.

USACO 2024 January Contest, Bronze. Problem 1. Majority Opinion.


Comments

There are no comments at the moment.