D - Semi Common Multiple

Score : $400$ points

Problem Statement

Given are a sequence $A= {a_1,a_2,......a_N}$ of $N$ positive even numbers, and an integer $M$.

Let a semi-common multiple of $A$ be a positive integer $X$ that satisfies the following condition for every $k$ $(1 \leq k \leq N)$:

• There exists a non-negative integer $p$ such that $X= a_k \times (p+0.5)$.

Find the number of semi-common multiples of $A$ among the integers between $1$ and $M$ (inclusive).

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq M \leq 10^9$
• $2 \leq a_i \leq 10^9$
• $a_i$ is an even number.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$

$a_1$ $a_2$ $...$ $a_N$

Output

Print the number of semi-common multiples of $A$ among the integers between $1$ and $M$ (inclusive).

2 50
6 10

2

• $15 = 6 \times 2.5 $
• $15 = 10 \times 1.5 $
• $45 = 6 \times 7.5 $
• $45 = 10 \times 4.5 $

Thus, $15$ and $45$ are semi-common multiples of $A$. There are no other semi-common multiples of $A$ between $1$ and $50$, so the answer is $2$.

3 100
14 22 40

0

The answer can be $0$.

5 1000000000
6 6 2 6 2

166666667