← 返回题目列表

AtCoder · abc150_d

D. 半公倍数

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给定一个序列 A= {a_1,a_2,......a_N} of N 正偶数和整数 M.

让 半公倍数 of A 是一个正整数 X 满足以下每个条件 k (1 \leq k \leq N):

  • 存在一个非负整数 p 这样 X= a_k \times (p+0.5).

求 的半公倍数的个数 A 之间的整数 1 和 M (含)。

约束

  • 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

输出

打印 的半倍数的个数 A 之间的整数 1 和 M (含)。


示例输入 1

2 50
6 10

示例输出 1

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

因此, 15 和 45 是半公倍数 A。没有其他半公倍数 A 之间 1 和 50,所以答案是 2.


示例输入 2

3 100
14 22 40

示例输出 2

0

答案可以是 0.


示例输入 3

5 1000000000
6 6 2 6 2

示例输出 3

166666667