分数: 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