分数: 500 点
问题陈述
给你整数 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.
查找整数的个数 x 之间 1 和 X,包含在内,这样 f(x)=0.
你被给予 T 测试用例;解决它们中的每一个。
约束
- 1\le T\le 2\times 10^5
- 1\le N\le 2\times 10^5
- 总和 N 所有测试用例最多 2\times 10^5.
- 1\le X\le 10^{18}
- 1\le A_i\le 10^{18}
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_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
考虑第一个测试用例。
例如,当 x=7, f(7)=(((7 \bmod 5) \bmod 2)\bmod 3)=(2\bmod 2)\bmod 3=0\bmod 3=0.
有四个整数 x 之间 1 和 7 这样 f(x)=0: x=2,4,5,7.