← 返回题目列表

AtCoder · abc466_f

F. 许多 Mod 计算

中文机器翻译题面 查看原题

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