题目描述

给定三个整数 $n,a,b$。考虑一个有 $n$ 个点的带权无向完全图，点编号为 $1$ 到 $n$。对于任意两个不同点 $u,v$，边权为

请你求从点 $a$ 到点 $b$ 的最短路长度。

输入格式

唯一一行包含三个整数 $n,a,b$。

输出格式

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

数据范围

• $2 \le n \le 10^9$
• $1 \le a,b \le n$
• $a \ne b$

样例 1 输入

10 9 8

样例 1 输出

7

样例 2 输入

100 16 27

样例 2 输出

10

提示

考虑第一个例子。

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

来源

Codeforces Round 2233 F - Shortest GCD Paths