多重取模计算(Many Mod Calculation)

题目描述

给定整数 $N, X$ 和长度为 $N$ 的正整数列 $A = (A_1, A_2, \ldots, A_N)$。

对于非负整数 $x$，定义 $f(x) = (\ldots((x \bmod A_1) \bmod A_2) \ldots) \bmod A_N$。

求满足 $f(x) = 0$ 的 $1$ 以上 $X$ 以下的整数 $x$ 的个数。

有 $T$ 个测试用例，请分别求出答案。

输入格式

输入从标准输入按以下格式给出：

T
（测试用例1）
（测试用例2）
\vdots
（测试用例T）

每个测试用例按以下格式给出：

N X
A_1 A_2 \ldots A_N

输出格式

每个测试用例的答案按顺序换行输出。

样例输入 #1

4
3 7
5 2 3
9 31415
9 9 8 2 4 4 3 5 3
1 1000000000000000000
1
9 20260405
3141 5926 5358 9793 2384 6264 3383 2795 288

样例输出 #1

4
17452
1000000000000000000
77403

第 1 个测试用例：$N=3, X=7, A=(5,2,3)$

例如 $x=7$ 时，$f(7) = (((7 \bmod 5) \bmod 2) \bmod 3) = ((2 \bmod 2) \bmod 3) = (0 \bmod 3) = 0$。

$1$ 以上 $7$ 以下满足 $f(x)=0$ 的整数 $x$ 有 $x=2,4,5,7$ 共 $4$ 个。

第 3 个测试用例：$N=1, X=10^{18}, A=(1)$

任意 $x$ 都有 $f(x) = x \bmod 1 = 0$，所以答案为 $10^{18}$。

数据范围

• $1 \leq T \leq 2 \times 10^5$
• $1 \leq N \leq 2 \times 10^5$（所有测试用例的 $N$ 之和 $\leq 2 \times 10^5$）
• $1 \leq X \leq 10^{18}$
• $1 \leq A_i \leq 10^{18}$
• 所有输入值为整数

知识点与难度

本题涉及的知识点从属于 GESP 五级，难度等级：⭐⭐⭐。

测试点分布