详细题解

1. 图的性质分析

首先对 $D$ 进行质因数分解，设 $D = \prod_{i=1}^{k} p_i^{c_i}$，其中 $p_i$ 为互不相同的质数。那么 $D$ 的任意约数 $x$ 可以唯一地表示为一个指数向量 $(a_1, a_2, \dots, a_k)$，其中 $0 \le a_i \le c_i$，并且 $x = \prod p_i^{a_i}$。

根据边的定义，两点 $x$ 与 $y$ 之间存在边，当且仅当它们的指数向量恰好在一个分量上相差 $1$（即某个 $a_j = b_j \pm 1$，其余分量相同）。并且边权值等于 $\prod_{i \neq j} (a_i + 1)$（假设 $x$ 的指数为 $a$，$y$ 的指数为 $b$，且 $a_j = b_j + 1$）。

由于每一步只能改变一个维度的指数且变化量为 $\pm 1$，从顶点 $v$（指数向量 $A$）到顶点 $u$（指数向量 $B$）的任意路径，其步数必须等于 $\sum_{i=1}^{k} |A_i - B_i|$，且该步数是路径长度的下界。因此我们只关心步数恰好等于该曼哈顿距离的路径。

2. 最小权值和与最优顺序

尽管步数固定，但不同顺序的边权之和不同。考虑我们要改变若干个质数的指数：有些需要减少（除法），有些需要增加（乘法）。设需要减少的指数差之和为 $S_{\text{down}} = \sum_{A_i > B_i} (A_i - B_i)$，需要增加的指数差之和为 $S_{\text{up}} = \sum_{A_i < B_i} (B_i - A_i)$。

引理：在所有步数等于 $S_{\text{down}} + S_{\text{up}}$ 的路径中，最小边权和可以通过先执行所有除法操作，再执行所有乘法操作达到。

简要证明：执行一次除法操作（减小某维度指数）时，该边的权值是当前其他维度“指数+1”的乘积。如果在做除法之前先做了某些乘法，那么其他维度的指数会变大，导致除法边的权值变大。反之，先做除法时，其他维度的指数保持较小的初始值，从而除法边权较小。乘法则无论如何都在除法之后，其权值无法被避免。因此先除后乘是最优顺序。而且，在除法步骤内部调换顺序，边权不变（因为边权与正在改变的维度指数无关，而其他维度指数尚未改变）；乘法步骤内部亦同。

因此，任意一条最短路径，其除法步骤和乘法步骤的内部顺序可以任意排列，而两类步骤之间的顺序固定（先除后乘）。

3. 路径计数

假设我们固定了：先从 $v$ 开始，连续执行 $S_{\text{down}}$ 次除法，每次将某个 $A_i > B_i$ 的维度的指数减 $1$；然后执行 $S_{\text{up}}$ 次乘法，每次将某个 $A_i < B_i$ 的维度的指数加 $1$。

对于除法阶段，我们需要进行 $S_{\text{down}}$ 步，其中有 $d_i = A_i - B_i$ 步是沿着维度 $i$ 进行的（若 $A_i > B_i$，否则 $d_i = 0$）。这些步骤可以任意排列，排列方式数为多重集的排列数：

$$\frac{S_{\text{down}}!}{\prod_{i} d_i!}$$

同理，乘法阶段的排列方式数为：

$$\frac{S_{\text{up}}!}{\prod_{i} m_i!}$$

其中 $m_i = B_i - A_i$（若 $B_i > A_i$，否则为 $0$）。

由于两阶段独立，总最短路径数量即为两者的乘积：

$$\text{Ans} = \frac{S_{\text{down}}!}{\prod d_i!} \times \frac{S_{\text{up}}!}{\prod m_i!} \pmod{998244353} $$

特别地，当 $v = u$ 时，$S_{\text{down}} = S_{\text{up}} = 0$，答案为 $1$（空路径）。

4. 实现细节

• 预处理：

  • 对 $D$ 进行质因数分解。$D \le 10^{15}$，使用 Pollard‑Rho 算法或优化过的试除法（只需试除到 $10^7$ 左右）均可。得到质数列表 $p_1,\dots,p_k$ 及其最大指数 $c_i$。$k$ 最多不超过 $15$。
  • 预处理阶乘与阶乘逆元，上界为最大可能的 $S_{\text{down}} + S_{\text{up}} \le \sum c_i$，而 $\sum c_i \le \log_2 D \approx 50$，因此阶乘数组只需开到 $100$ 左右即可。

• 处理询问：
  对于每个询问 $(v, u)$：

  • 计算 $v$ 和 $u$ 在每个质数 $p_i$ 下的指数 $a_i$ 和 $b_i$。由于 $v,u$ 都是 $D$ 的约数，可以通过不断除以 $p_i$ 得到指数。
  • 计算 $d_i = \max(0, a_i - b_i)$，$m_i = \max(0, b_i - a_i)$。
  • 计算 $S_d = \sum d_i$，$S_m = \sum m_i$。
  • 若 $S_d = 0$ 且 $S_m = 0$，输出 $1$；否则答案为：$$\text{fact}[S_d] \cdot \text{invfact}[S_m] \cdot \prod \text{invfact}[d_i] \cdot \prod \text{invfact}[m_i] \pmod{M} $$

• 复杂度：
  质因数分解 $O(\sqrt{D})$ 或 $O(D^{1/4})$；每个询问 $O(k)$，总 $O(q \cdot k)$，足以通过。

5. 模数

注意题目给定的模数为 $998244353$，这是常见的质数，阶乘逆元可直接用费马小定理计算。

---