Home

Contest: Task: Related: TaskC TaskE

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).

Sample Input 1

2 50
6 10

Sample Output 1

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

Sample Input 2

3 100
14 22 40

Sample Output 2

0

The answer can be $0$.

Sample Input 3

5 1000000000
6 6 2 6 2

Sample Output 3

166666667