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:

Copy

2 50
6 10

Salida de ejemplo 1:

Copy

$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:

Copy

3 100
14 22 40

Salida de ejemplo 2:

Copy

Entrada de ejemplo 3:

Copy

5 1000000000
6 6 2 6 2

Salida de ejemplo 3:

Copy

166666667

Comments

2

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

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