CF1750D Count GCD

给定两个整数 $n$ 和 $m$，以及一个长度为 $n$ 的数组 $a$。对于每个 $1 \le i \le n$，都有 $1 \le a_i \le m$。 你的任务是计算有多少个不同的长度为 $n$ 的数组 $b$ 满足以下条件： - 对于每个 $1 \le i \le n$，都有 $1 \le b_i \le m$； - 对于每个 $1 \le i \le n$，都有 $\gcd(b_1, b_2, b_3, \ldots, b_i) = a_i$。 这里 $\gcd(a_1, a_2, \dots, a_i)$ 表示整数 $a_1, a_2, \ldots, a_i$ 的最大公约数。 由于答案可能很大，请输出答案对 $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$ 的长度和元素的最大可能值。 每组测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le m$）——数组 $a$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示满足条件的不同数组的数量。由于答案可能很大，请输出对 $998\,244\,353$ 取模后的结果。

在第一个测试用例中，可能的数组 $b$ 有： - $[4,2,1]$； - $[4,2,3]$； - $[4,2,5]$。 在第二个测试用例中，唯一满足条件的数组是 $[1,1]$。 在第三个测试用例中，可以证明不存在满足条件的数组。 由 ChatGPT 4.1 翻译