← 返回题目列表

Codeforces · 2233/F

F. 最短 GCD 路径

中文机器翻译题面 查看原题

给你三个整数 $$$n$$$、$$$a$$$、$$$b$$$。考虑一个具有 $$$n$$$ 顶点的加权无向图,其中对于每对不同的顶点 $$$(u, v)$$$ 都有一条具有权重的边:

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

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

在此图中找到从顶点 $$$a$$$ 到顶点 $$$b$$$ 的最短路径。

输入

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

输出

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

示例

输入
复制

10 9 8

输出
复制

7

输入
复制

100 16 27

输出
复制

10

输入
复制

100 55 11

输出
复制

5

注意

考虑第一个例子。

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