309880: CF1750D. Count GCD
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Count GCD
题意翻译
给定 $n,m$ ，和一个数列 $a$，问你有多少种方案构造一个长度为 $n$ 的序列 $b$，满足下的条件： 1. $\forall i,b_i\in[1,m];$ 2. $\displaystyle \forall i,\gcd_{j=1}^i b_i=a_i.$题目描述
You are given two integers $ n $ and $ m $ and an array $ a $ of $ n $ integers. For each $ 1 \le i \le n $ it holds that $ 1 \le a_i \le m $ . Your task is to count the number of different arrays $ b $ of length $ n $ such that: - $ 1 \le b_i \le m $ for each $ 1 \le i \le n $ , and - $ \gcd(b_1,b_2,b_3,...,b_i) = a_i $ for each $ 1 \le i \le n $ . Here $ \gcd(a_1,a_2,\dots,a_i) $ denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $ a_1,a_2,\ldots,a_i $ . Since this number can be too large, print it modulo $ 998\,244\,353 $ .输入输出格式
输入格式
Each test consist of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains two integers $ n $ and $ m $ ( $ 1 \le n \le 2 \cdot 10^5 $ , $ 1 \le m \le 10^9 $ ) — the length of the array $ a $ and the maximum possible value of the element. The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le m $ ) — the elements of the array $ a $ . It is guaranteed that the sum of $ n $ across all test cases doesn't exceed $ 2 \cdot 10^5 $ .
输出格式
For each test case, print a single integer — the number of different arrays satisfying the conditions above. Since this number can be large, print it modulo $ 998\,244\,353 $ .
输入输出样例
输入样例 #1
5
3 5
4 2 1
2 1
1 1
5 50
2 3 5 2 3
4 1000000000
60 30 1 1
2 1000000000
1000000000 2输出样例 #1
3
1
0
595458194
200000000说明
In the first test case, the possible arrays $ b $ are: - $ [4,2,1] $ ; - $ [4,2,3] $ ; - $ [4,2,5] $ . In the second test case, the only array satisfying the demands is $ [1,1] $ . In the third test case, it can be proven no such array exists.Input
题意翻译
给定 $n,m$ ，和一个数列 $a$，问你有多少种方案构造一个长度为 $n$ 的序列 $b$，满足下的条件： 1. $\forall i,b_i\in[1,m];$ 2. $\displaystyle \forall i,\gcd_{j=1}^i b_i=a_i.$Output
题目大意：
给定两个整数 $ n $ 和 $ m $，以及一个长度为 $ n $ 的整数数组 $ a $，要求计算有多少种不同的长度为 $ n $ 的数组 $ b $ 满足以下条件：
1. 对于每个 $ 1 \le i \le n $，有 $ 1 \le b_i \le m $；
2. 对于每个 $ 1 \le i \le n $，有 $ \gcd(b_1,b_2,\ldots,b_i) = a_i $。
其中，$ \gcd(b_1,b_2,\ldots,b_i) $ 表示整数 $ b_1,b_2,\ldots,b_i $ 的最大公约数（GCD）。
由于这个数目可能非常大，所以需要将结果模 $ 998\,244\,353 $ 后输出。
输入输出数据格式：
输入格式：
- 第一行包含一个整数 $ t $（$ 1 \le t \le 100 $），表示测试用例的数量。
- 每个测试用例包含两行：
- 第一行包含两个整数 $ n $ 和 $ m $（$ 1 \le n \le 2 \cdot 10^5 $，$ 1 \le m \le 10^9 $），分别表示数组 $ a $ 的长度和数组 $ b $ 元素的最大可能值。
- 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 1 \le a_i \le m $），表示数组 $ a $ 的元素。
输出格式：
- 对于每个测试用例，输出一个整数，表示满足条件的不同数组 $ b $ 的数量，模 $ 998\,244\,353 $ 后的结果。
输入输出样例：
输入样例 #1：
```
5
3 5
4 2 1
2 1
1 1
5 50
2 3 5 2 3
4 1000000000
60 30 1 1
2 1000000000
1000000000 2
```
输出样例 #1：
```
3
1
0
595458194
200000000
```题目大意： 给定两个整数 $ n $ 和 $ m $，以及一个长度为 $ n $ 的整数数组 $ a $，要求计算有多少种不同的长度为 $ n $ 的数组 $ b $ 满足以下条件： 1. 对于每个 $ 1 \le i \le n $，有 $ 1 \le b_i \le m $； 2. 对于每个 $ 1 \le i \le n $，有 $ \gcd(b_1,b_2,\ldots,b_i) = a_i $。 其中，$ \gcd(b_1,b_2,\ldots,b_i) $ 表示整数 $ b_1,b_2,\ldots,b_i $ 的最大公约数（GCD）。 由于这个数目可能非常大，所以需要将结果模 $ 998\,244\,353 $ 后输出。 输入输出数据格式： 输入格式： - 第一行包含一个整数 $ t $（$ 1 \le t \le 100 $），表示测试用例的数量。 - 每个测试用例包含两行： - 第一行包含两个整数 $ n $ 和 $ m $（$ 1 \le n \le 2 \cdot 10^5 $，$ 1 \le m \le 10^9 $），分别表示数组 $ a $ 的长度和数组 $ b $ 元素的最大可能值。 - 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 1 \le a_i \le m $），表示数组 $ a $ 的元素。 输出格式： - 对于每个测试用例，输出一个整数，表示满足条件的不同数组 $ b $ 的数量，模 $ 998\,244\,353 $ 后的结果。 输入输出样例： 输入样例 #1： ``` 5 3 5 4 2 1 2 1 1 1 5 50 2 3 5 2 3 4 1000000000 60 30 1 1 2 1000000000 1000000000 2 ``` 输出样例 #1： ``` 3 1 0 595458194 200000000 ```
给定两个整数 $ n $ 和 $ m $，以及一个长度为 $ n $ 的整数数组 $ a $，要求计算有多少种不同的长度为 $ n $ 的数组 $ b $ 满足以下条件：
1. 对于每个 $ 1 \le i \le n $，有 $ 1 \le b_i \le m $；
2. 对于每个 $ 1 \le i \le n $，有 $ \gcd(b_1,b_2,\ldots,b_i) = a_i $。
其中，$ \gcd(b_1,b_2,\ldots,b_i) $ 表示整数 $ b_1,b_2,\ldots,b_i $ 的最大公约数（GCD）。
由于这个数目可能非常大，所以需要将结果模 $ 998\,244\,353 $ 后输出。
输入输出数据格式：
输入格式：
- 第一行包含一个整数 $ t $（$ 1 \le t \le 100 $），表示测试用例的数量。
- 每个测试用例包含两行：
- 第一行包含两个整数 $ n $ 和 $ m $（$ 1 \le n \le 2 \cdot 10^5 $，$ 1 \le m \le 10^9 $），分别表示数组 $ a $ 的长度和数组 $ b $ 元素的最大可能值。
- 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 1 \le a_i \le m $），表示数组 $ a $ 的元素。
输出格式：
- 对于每个测试用例，输出一个整数，表示满足条件的不同数组 $ b $ 的数量，模 $ 998\,244\,353 $ 后的结果。
输入输出样例：
输入样例 #1：
```
5
3 5
4 2 1
2 1
1 1
5 50
2 3 5 2 3
4 1000000000
60 30 1 1
2 1000000000
1000000000 2
```
输出样例 #1：
```
3
1
0
595458194
200000000
```题目大意： 给定两个整数 $ n $ 和 $ m $，以及一个长度为 $ n $ 的整数数组 $ a $，要求计算有多少种不同的长度为 $ n $ 的数组 $ b $ 满足以下条件： 1. 对于每个 $ 1 \le i \le n $，有 $ 1 \le b_i \le m $； 2. 对于每个 $ 1 \le i \le n $，有 $ \gcd(b_1,b_2,\ldots,b_i) = a_i $。 其中，$ \gcd(b_1,b_2,\ldots,b_i) $ 表示整数 $ b_1,b_2,\ldots,b_i $ 的最大公约数（GCD）。 由于这个数目可能非常大，所以需要将结果模 $ 998\,244\,353 $ 后输出。 输入输出数据格式： 输入格式： - 第一行包含一个整数 $ t $（$ 1 \le t \le 100 $），表示测试用例的数量。 - 每个测试用例包含两行： - 第一行包含两个整数 $ n $ 和 $ m $（$ 1 \le n \le 2 \cdot 10^5 $，$ 1 \le m \le 10^9 $），分别表示数组 $ a $ 的长度和数组 $ b $ 元素的最大可能值。 - 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 1 \le a_i \le m $），表示数组 $ a $ 的元素。 输出格式： - 对于每个测试用例，输出一个整数，表示满足条件的不同数组 $ b $ 的数量，模 $ 998\,244\,353 $ 后的结果。 输入输出样例： 输入样例 #1： ``` 5 3 5 4 2 1 2 1 1 1 5 50 2 3 5 2 3 4 1000000000 60 30 1 1 2 1000000000 1000000000 2 ``` 输出样例 #1： ``` 3 1 0 595458194 200000000 ```