Divisor Paths 题解（浓缩版）

核心转化

设 $D = p_1^{a_1}\cdots p_k^{a_k}$，每个因子对应指数向量 $(b_1,\dots,b_k)$。
边连接指数向量相差一个单位（单维 $\pm1$），边权 $w = \tau(x)-\tau(y)$，其中 $\tau(x)=\prod(b_i+1)$。

关键结论

对于询问 $(v,u)$，设 $g = \gcd(v,u)$，指数 $g_i = \min(v_i,u_i)$：

1. 最短路径长度 $= \tau(v) + \tau(u) - 2\tau(g)$
2. 所有最短路径 必须先下降（$v \to g$）再上升（$g \to u$）
3. 路径计数：
   • 下降：需减少 $d_i = v_i - g_i$ 步，方案数 $= \dfrac{(\sum d_i)!}{\prod d_i!}$
   • 上升：需增加 $e_i = u_i - g_i$ 步，方案数 $= \dfrac{(\sum e_i)!}{\prod e_i!}$
   • 答案 $= \dfrac{(\sum d_i)!}{\prod d_i!} \cdot \dfrac{(\sum e_i)!}{\prod e_i!} \pmod{998244353}$

算法步骤

1. 质因数分解 $D$，得素数 $p_i$ 及最大指数 $a_i$
2. 预处理阶乘和逆元到 $S_{\max} = \sum a_i \le 60$
3. 每个询问：
   • 对每个 $p_i$，计算 $v,u$ 中的指数 $v_i,u_i$
   • 令 $d_i = \max(0, v_i-u_i)$，$e_i = \max(0, u_i-v_i)$
   • 计算 $S_d = \sum d_i$，$S_e = \sum e_i$
   • 输出 $fact[S_d] \cdot fact[S_e] \cdot \prod inv\_fact[d_i] \cdot \prod inv\_fact[e_i]$

复杂度

• 分解 $O(\sqrt{D})$ 或 Pollard-Rho
• 每个询问 $O(k)$，$k \le 15$，$q \le 3\times10^5$