AT_abc150_d [ABC150D] Semi Common Multiple

题目描述

给定一个长度为 $N$ 的正整数序列 $A = \{a_1, a_2, \ldots, a_N\}$，其中每个 $a_i$ 都是偶数，以及一个整数 $M$。

对于任意的 $k$（$1 \leq k \leq N$），如果存在一个非负整数 $p$，使得 $X = a_k \times (p + 0.5)$，则称正整数 $X$ 为 $A$ 的“半公倍数”。

请你求出 $1$ 到 $M$ 之间（包含 $1$ 和 $M$）的正整数中，有多少个是 $A$ 的半公倍数。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M$ $a_1$ $a_2$ $\ldots$ $a_N$

输出格式

输出 $1$ 到 $M$ 之间 $A$ 的半公倍数的个数。

输入输出样例 #1

输入 #1

2 50
6 10

输出 #1

2

输入输出样例 #2

输入 #2

3 100
14 22 40

输出 #2

0

输入输出样例 #3

输入 #3

5 1000000000
6 6 2 6 2

输出 #3

166666667

说明/提示

限制条件

• $1 \leq N \leq 10^5$
• $1 \leq M \leq 10^9$
• $2 \leq a_i \leq 10^9$
• 每个 $a_i$ 都是偶数。
• 输入均为整数。

样例解释 1

• $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$。

样例解释 2

答案也有可能为 $0$。

由 ChatGPT 4.1 翻译