多次取模计算AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)You are given integers $N,X$ and a length-$N$ sequence of positive integers $A=(A_1,A_2,\ldots,A_N)$.
给定整数 $N,X$ 以及一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\ldots,A_N)$。AI (CI翻译)
For a non-negative integer $x$, define $f(x)=(\ldots((x \bmod A_1) \bmod A_2) \ldots ) \bmod A_N$.
对于非负整数 $x$，定义 $f(x)=(\ldots((x \bmod A_1) \bmod A_2) \ldots ) \bmod A_N$。AI (CI翻译)
Find the number of integers $x$ between $1$ and $X$, inclusive, such that $f(x)=0$.
请求出满足 $f(x)=0$ 且 $x$ 在 $1$ 到 $X$（含）之间的整数 $x$ 的数量。AI (CI翻译)
You are given $T$ test cases; solve each of them.
给定 $T$ 组测试数据，请分别求解每组数据。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$1\le T\le 2\times 10^5$$1\le N\le 2\times 10^5$- The sum of
$N$over all test cases is at most$2\times 10^5$. $1\le X\le 10^{18}$$1\le A_i\le 10^{18}$- All input values are integers.
$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}$- 所有输入值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入按以下格式给出：AI (CI翻译)
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_TT
\text{case}_1
\text{case}_2
\vdots
\text{case}_TEach test case is given in the following format:
每组测试数据按以下格式给出：AI (CI翻译)
N X
A_1 A_2 \ldots A_NN X
A_1 A_2 \ldots A_NOutput
输出格式
AI (CI翻译)Output the answers for the test cases in order, separated by newlines.
按测试数据的顺序输出答案，每组答案占一行。AI (CI翻译)
样例
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
4
17452
1000000000000000000
77403
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。