在解决本题的过程中，有一步选择 $u$ 和 $v$ 的共同终点，然后才开始计算路径方案数。

题解区中的题解全部选择走到 $\gcd(u,v)$ 但却没有给出具体证明。虽然完全可以感性理解然后 A 掉本题，但我还是很好奇能不能证明选择 $\gcd$ 的路径比选择 $\operatorname{lcm}$ 的路径要更短。

有思路、有兴趣的大佬可以来让我膜一下分享一下你们的观点吗？

我自己举了一个例子，不知道对不对

假设

$$u=p_1^{k_1}\times p_2^{k_2}\times p_3^{k_3}\times p_4^{k_4}$$ $$v = p_1^{e_1}\times p_2^{e_2}\times p_3^{e_3}\times p_4^{e_4}$$ \operatorname{lcm}(u,v) = p_1^{k_1}\times p_2^{e_2}\times p_3^{e_3}\times p_4^{k_4}$$

\gcd(u,v) = p_1^{e_1}\times p_2^{k_2}\times p_3^{k_3}\times p_4^{e_4}

其中 $p_i$ 均为质数，以下 $\sigma_0(x)$ 表示为 $x$ 中约数的个数 那么：

\begin{aligned} \sigma_0(\text{lcm}) &= (k_1+1)\times(e_2+1)\times(e_3+1)\times (k_4+1)\ \end{aligned}

$$$$

\sigma_0(\text{gcd})= (e_1+1)\times(k_2+1)\times(k_3+1)\times (e_4+1)

$$$$

\sigma_0(u) = (k_1+1)\times(k_2+1)\times(k_3+1)\times (k_4+1)

$$$$

\sigma_0(v) = (e_1+1)\times(e_2+1)\times(e_3+1)\times (e_4+1)

$$------------$$

w_1=\sigma_0(u)-\sigma_0(\gcd)+\sigma_0(v)-\sigma_0(\gcd)

$$=(e_2+1)(e_3+1)[(k_1+1)(k_4+1)-(e_1+1)(e_4+1)]+(k_1+1)(k_4+1)[(e_2+1)(e_3+1)-(k_2+1)(k_3+1)]

---

$$w_2=\sigma_0(\text{lcm})-\sigma_0(u)+\sigma_0(\text{lcm})-\sigma_0(v)$$ $$=(k_2+1)(k_3+1)[(k_1+1)(k_4+1)-(e_1+1)(e_4+1)]+(e_1+1)(e_4+1)[(e_2+1)(e_3+1)-(k_2+1)(k_3+1)]$$

---

$$\because k_1 > e_1,e2>k_2,e_3>k_3,k_4>e_4$$ $$\therefore w_2-w_1>0,w_2>w_1$$

所以得证，不知道对不对。

欢迎各路大佬来虐爆我！让我膜爆！ 分享你们的想法