配点 : $400$ 点

問題文

長さ $N$ の偶数からなる正の整数列 $A= {a_1,a_2,...,a_N}$ と、整数 $M$ が与えられます。

任意の $k(1 \leq k \leq N)$ に対して以下の条件を満たす正の整数 $X$ を $A$ の「半公倍数」と定義します。

• $X= a_k \times (p+0.5)$ を満たす負でない整数 $p$ が存在する。

$1$ 以上 $M$ 以下の整数のうちの $A$ の半公倍数の個数を求めてください。

制約

• $1 \leq N \leq 10^5$
• $1 \leq M \leq 10^9$
• $2 \leq a_i \leq 10^9$
• $a_i$ は偶数である。
• 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

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

出力

$1$ 以上 $M$ 以下の整数のうちの $A$ の半公倍数の個数を出力せよ。

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$

より、$15,45$ は $A$ の半公倍数です。$1$ 以上 $50$ 以下の整数に他に $A$ の半公倍数はないので、答えは $2$ となります。

3 100
14 22 40

0

答えが $0$ の場合もあります。

5 1000000000
6 6 2 6 2

166666667