Multiplos semi-comunes


Submit solution

Points: 100
Time limit: 1.0s
Memory limit: 256M

Authors:
Problem type
Allowed languages
C, C++, Java, Python, VB

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

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

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

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

Límites:

1 \leq N \leq 10^5

1 \leq M \leq 10^9

2 \leq a_i \leq 10^9

a_i es un número par

Entrada:

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

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

Salida:

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

Entrada de ejemplo 1:

2 50
6 10

Salida de ejemplo 1:

2

15 = 6 * 2.5

15 = 10 * 1.5

45 = 6 * 7.5

45 = 10 * 4.5

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

Entrada de ejemplo 2:

3 100
14 22 40

Salida de ejemplo 2:

0

Entrada de ejemplo 3:

5 1000000000
6 6 2 6 2

Salida de ejemplo 3:

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.