CF2233F Shortest GCD Paths

给定三个整数 $n$、$a$、$b$。考虑一个有 $n$ 个顶点的带权无向图，对于每对不同的顶点 $(u,v)$，都有一条边，其权值为： $$ w(u, v) = \frac{\max(u, v)}{\gcd(u, v)} $$ 其中 $\gcd(x, y)$ 表示整数 $x$ 与 $y$ 的最大公约数。 请你求出从顶点 $a$ 到顶点 $b$ 的最短路径。

一行包含三个整数 $n$、$a$、$b$，满足 $2 \leq n \leq 10^{9}$，$1 \leq a, b \leq n$，且 $a \neq b$。

输出一个整数，表示从顶点 $a$ 到顶点 $b$ 的最短路径长度。

以第一个样例为例。 最短路径是 $9 \to 6 \to 8$，总花费为 $w(9,6) + w(6,8) = 3 + 4 = 7$。 由 ChatGPT 5 翻译