Multiplos semi-comunes

Points: 100

Time limit: 1.0s

Memory limit: 256M

Authors:

FrankHG, Albe, mdario

Problem type

Allowed languages

C, C++, Java, Python, VB

Tienes una secuencia $A = a_1, a_2, ..., a_N$ ~A = a_1, a_2, ..., a_N~ de $N$ ~N~ números pares positivos y un entero $M$ ~M~.

Un múltiplo semi-común de $A$ ~A~ es un entero positivo $X$ ~X~ tal que cumpla con la siguiente condición para cada $k$ ~k~ $(1 \leq k \leq N)$ ~(1 \leq k \leq N)~:

Existe un entero no negativo $p$ ~p~ tal que $X = a_k * (p + 0.5)$ ~X = a_k * (p + 0.5)~.

Encuentra el número de múltiplos semi-comunes de $A$ ~A~ entre todos los enteros entre $1$ ~1~ y $M$ ~M~ (inclusive).

Límites:

$1 \leq N \leq 10^5$ ~1 \leq N \leq 10^5~

$1 \leq M \leq 10^9$ ~1 \leq M \leq 10^9~

$2 \leq a_i \leq 10^9$ ~2 \leq a_i \leq 10^9~

$a_i$ ~a_i~ es un número par

Entrada:

La primera línea contiene dos números $N$ ~N~ y $M$ ~M~.

La segunda línea contiene la secuencia $A$ ~A~ de $N$ ~N~ números.

Salida:

Imprime el número de múltiplos semi-comunes de $A$ ~A~ entre los enteros entre $1$ ~1~ y $M$ ~M~ (inclusive).

Entrada de ejemplo 1:

2 50
6 10

Salida de ejemplo 1:

$15 = 6 * 2.5$ ~15 = 6 * 2.5~

$15 = 10 * 1.5$ ~15 = 10 * 1.5~

$45 = 6 * 7.5$ ~45 = 6 * 7.5~

$45 = 10 * 4.5$ ~45 = 10 * 4.5~

Así que $15$ ~15~ y $45$ ~45~ son múltiplos semi-comunes de $A$ ~A~. No hay otros múltiplos semi-comunes de $A$ ~A~ entre $1$ ~1~ y $50$ ~50~, así que la respuesta es $2$ ~2~.

Entrada de ejemplo 2:

3 100
14 22 40

Salida de ejemplo 2:

Entrada de ejemplo 3:

5 1000000000
6 6 2 6 2

Salida de ejemplo 3:

166666667

Comments

1

linkyless commented on May 24, 2022, 1:21 a.m. ← edit 2 →

En el tercer ejemplo, mi salida es 166666666 por alguna razón.