Semi Common Multiple

题目描述

给定一个由 $N$ 个正偶数组成的序列 $A= {a_1,a_2,......a_N}$，以及一个整数 $M$。 称正整数 $X$ 为 $A$ 的一个 半公倍数，当且仅当对任意 $k$ $(1 \leq k \leq N)$ 满足以下条件：

存在非负整数 $p$ 使得 $X= a_k \times (p+0.5)$。

求在区间 $1$ 到 $M$（含端点）之间的整数中，作为 $A$ 的半公倍数的个数。

输入格式

输入以标准输入给出，格式如下： $N$ $M$ $a_1$ $a_2$ $...$ $a_N$

输出格式

输出区间 $1$ 到 $M$（含端点）之间作为 $A$ 的半公倍数的整数个数。

2 50
6 10

2

3 100
14 22 40

0

5 1000000000
6 6 2 6 2

166666667

提示

$1 \leq N \leq 10^5$ $1 \leq M \leq 10^9$ $2 \leq a_i \leq 10^9$ $a_i$ 是偶数。 输入中的所有数值均为整数。$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$ 之间没有其他的半公倍数，所以答案为 $2$。
答案也可以为 $0$。

标签: AtCoder|abc150D

来源

AtCoder|abc150D