Problem
多组数据。
每组数据给定两个整数 \(n\)，\(m\) 和一个数列 \(b\)，问有多少种方案构造一个长度为 \(n\) 的序列 \(a\)，满足 \(1 \le a_i \le m\) 求 \(gcd(a_1,a_2,\cdots,a_i) = b_i\)，答案对 \(998244353\) 取模。
Input
第一行输入 \(t\)，表示数据组数。
每组数据第一行是两个整数 \(n\)，\(m\)。
每组数据第二行输入 \(n\) 个整数 \(b_1,b_2,\cdots,b_n\)
Output
输出 \(t\) 行，每行输出一个整数表示答案。
Sample
Input 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
Output 1
3
1
0
595458194
200000000
Solution
首先对于 \(\forall 2 \le i \le n\)，如果 \(b_{i-1}\) 不是 \(b_i\) 的倍数，显然无解。
因为 \(b_i=gcd(b_{i-1},a_i)\)，所以 \(gcd(\dfrac{b_{i-1}}{b_i},\dfrac{a_i}{b_i})=1\)。
而 \(a_i\) 的取值在 \([1,m]\) 之间，那我们就是需要在 \([1,\dfrac{m}{b_i}]\) 中统计出与 \(\dfrac{b_{i-1}}{b_i}\) 互质的数的个数。
考虑容斥，我们令 \(g\) 来表示 \(\dfrac{b_{i-1}}{b_i}\)，每次暴力求出 \(g\) 的质因子，然后枚举选取质因子的状态，统计答案即可。
由于 \(b_{i-1}\) 是 \(b_i\) 的倍数，\(1 \le b_i \le m \le 10^9\)，那么如果 \(b_{i-1} \neq b_i\)，\(b_{i-1}\) 至少是 \(b_i\) 的 \(2\) 倍，所以说 \(b_{i-1} \neq b_i\) 的情况最多只有 \(log\) 次，容斥的次数大幅减少。
而对于 \(b_{i-1}=b_i\) 的情况，\(有g=1\)，没有质因子，自然就不会容斥来统计答案。
代码：
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int kmax = 2e5 + 3;
const int Mod = 998244353;
int t, n, m;
int b[kmax];
int p[kmax], pc;
long long res;
long long Calc(int x, int y) { // 容斥
pc = 0;
int j = y;
for (int i = 2; i * i <= y; i++) { // 筛质因子
if (j % i) continue;
p[++pc] = i;
for (; j % i == 0; j /= i) {
}
}
if (j > 1) p[++pc] = j;
long long res = 0;
for (int i = 0; i < 1 << pc; i++) { // 枚举状态
int op = 1;
long long v = 1;
for (int j = 0; j < pc; j++) {
if (i & 1 << j) {
op *= -1;
v *= p[j + 1];
}
}
res += op * x / v;
}
return res;
}
void Solve() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> b[i];
}
res = 1;
for (int i = 2; i <= n; i++) {
if (b[i - 1] % b[i]) { // 无解
cout << 0 << '\n';
return;
}
res = res * Calc(m / b[i], b[i - 1] / b[i]) % Mod; // 统计答案
}
cout << res << '\n';
}
int main() {
cin >> t;
while (t--) {
Solve();
}
return 0;
}