CF2233F.Shortest GCD Paths

You are given three integers $n$, $a$, $b$. Consider a weighted undirected graph with $n$ vertices, where for every pair of distinct vertices $(u, v)$ there is an edge with weight:

$$w(u, v) = \\frac{\\max(u, v)}{\\gcd(u, v)}$$

Here $\gcd(x, y)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$.

Find the shortest path from vertex $a$ to vertex $b$ in this graph.

给你三个整数 $n$、$a$、$b$。考虑一个含 $n$ 个顶点的带权无向图，其中对任意一对不同的顶点 $(u, v)$，均存在一条边，其权重为：

$$w(u, v) = \frac{\max(u, v)}{\gcd(u, v)}$$

这里 $\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数（GCD）。

求该图中从顶点 $a$ 到顶点 $b$ 的最短路径。

The only line contains three integers $n$, $a$, $b$ ($2 \le n \le 10^{9}, 1 \le a, b \le n, a \neq b$).

唯一一行包含三个整数 $n$、$a$、$b$（$2 \le n \le 10^{9}$，$1 \le a, b \le n$，$a \neq b$）。

Print one integer — the length of the shortest path from vertex $a$ to vertex $b$.

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

Consider the first example.

The shortest path in it is $9 \to 6 \to 8$ with total cost $w(9, 6) + w(6, 8) = 3 + 4 = 7$.

考虑第一个例子。

其中最短路径为 $9 \to 6 \to 8$，总代价为 $w(9, 6) + w(6, 8) = 3 + 4 = 7$。