/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 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 と定義します。
f(x)=0 となる 1 以上 X 以下の整数 x がいくつ存在するか求めてください。
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
1 番目のテストケースについて考えます。
例えば x=7 のとき f(7)=(((7 \bmod 5) \bmod 2)\bmod 3)=(2\bmod 2)\bmod 3=0\bmod 3=0 となります。
f(x)=0 となる 1 以上 7 以下の整数 x は x=2,4,5,7 の 4 つです。
Score : 500 points
Problem Statement
You are given integers N,X and a length-N sequence of positive integers A=(A_1,A_2,\ldots,A_N).
For a non-negative integer x, define f(x)=(\ldots((x \bmod A_1) \bmod A_2) \ldots ) \bmod A_N.
Find the number of integers x between 1 and X, inclusive, such that f(x)=0.
You are given T test cases; solve each of them.
Constraints
- 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.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N X A_1 A_2 \ldots A_N
Output
Output the answers for the test cases in order, separated by newlines.
Sample Input 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
Sample Output 1
4 17452 1000000000000000000 77403
Consider the first test case.
For example, when x=7, f(7)=(((7 \bmod 5) \bmod 2)\bmod 3)=(2\bmod 2)\bmod 3=0\bmod 3=0.
There are four integers x between 1 and 7 such that f(x)=0: x=2,4,5,7.