CF1866B Battling with Numbers

在期中考试期间前往校园的路上，Chaneka 想到了两个正整数 $X$ 和 $Y$。由于这两个整数可能非常大，因此它们都用质因数分解的形式表示： - $X = A_1^{B_1} \times A_2^{B_2} \times \ldots \times A_N^{B_N}$（每个 $A_i$ 是质数，每个 $B_i$ 是正整数，且 $A_1 < A_2 < \ldots < A_N$） - $Y = C_1^{D_1} \times C_2^{D_2} \times \ldots \times C_M^{D_M}$（每个 $C_j$ 是质数，每个 $D_j$ 是正整数，且 $C_1 < C_2 < \ldots < C_M$） Chaneka 在路上思考这两个整数太久了，于是她的朋友催促她“Gece, deh!”（快点），以免迟到参加考试。 因此，Chaneka 想出了一个问题：有多少对正整数 $p$ 和 $q$ 满足 $\text{LCM}(p, q) = X$ 且 $\text{GCD}(p, q) = Y$。由于答案可能非常大，请输出答案对 $998\,244\,353$ 取模后的结果。 注意： - $\text{LCM}(p, q)$ 表示同时被 $p$ 和 $q$ 整除的最小正整数。 - $\text{GCD}(p, q)$ 表示同时整除 $p$ 和 $q$ 的最大正整数。

第一行包含一个整数 $N$（$1 \leq N \leq 10^5$）——$X$ 的质因数分解中不同质数的个数。 第二行包含 $N$ 个整数 $A_1, A_2, A_3, \ldots, A_N$（$2 \leq A_1 < A_2 < \ldots < A_N \leq 2 \cdot 10^6$，每个 $A_i$ 是质数）——$X$ 的质因数分解中的质数。 第三行包含 $N$ 个整数 $B_1, B_2, B_3, \ldots, B_N$（$1 \leq B_i \leq 10^5$）——$X$ 的质因数分解中的指数。 第四行包含一个整数 $M$（$1 \leq M \leq 10^5$）——$Y$ 的质因数分解中不同质数的个数。 第五行包含 $M$ 个整数 $C_1, C_2, C_3, \ldots, C_M$（$2 \leq C_1 < C_2 < \ldots < C_M \leq 2 \cdot 10^6$，每个 $C_j$ 是质数）——$Y$ 的质因数分解中的质数。 第六行包含 $M$ 个整数 $D_1, D_2, D_3, \ldots, D_M$（$1 \leq D_j \leq 10^5$）——$Y$ 的质因数分解中的指数。

输出一个整数，表示满足 $\text{LCM}(p, q) = X$ 且 $\text{GCD}(p, q) = Y$ 的正整数对 $(p, q)$ 的个数，对 $998\,244\,353$ 取模。

在第一个样例中，整数如下： - $X = 2^2 \times 3^1 \times 5^1 \times 7^2 = 2940$ - $Y = 3^1 \times 7^1 = 21$ 所有可能的 $(p, q)$ 如下： - $p = 21$，$q = 2940$ - $p = 84$，$q = 735$ - $p = 105$，$q = 588$ - $p = 147$，$q = 420$ - $p = 420$，$q = 147$ - $p = 588$，$q = 105$ - $p = 735$，$q = 84$ - $p = 2940$，$q = 21$ 在第三个样例中，整数如下： - $X = 2^1 \times 5^1 = 10$ - $Y = 2^1 \times 3^1 = 6$ 不存在同时满足 $\text{LCM}(p, q) = 10$ 且 $\text{GCD}(p, q) = 6$ 的 $(p, q)$。 由 ChatGPT 4.1 翻译