← 返回题目列表

Codeforces · 2038/K

K. 网格行走

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

你有一个 $$$n \times n$$$ 网格和两个整数 $$$a$$$ 和 $$$b$$$。行和列的编号都是从 $$$1$$$ 到 $$$n$$$。我们将第 $$$i$$$ 行和第 $$$j$$$ 列交叉处的单元格表示为 $$$(i, j)$$$。

您正站在单元格 $$$(1, 1)$$$ 中,并且想要移至单元格 $$$(n, n)$$$。

假设您位于单元格 $$$(i, j)$$$ 中;在一步中,您可以移动到单元格 $$$(i, j + 1)$$$ 或移动到单元格 $$$(i + 1, j)$$$(如果相应的单元格存在)。

让我们将单元格 $$$(i, j)$$$ 的成本定义为 $$$c(i, j) = \gcd(i, a) + \gcd(j, b)$$$ (这里,$$$\gcd(x,y)$$$ 表示 $$$x$$$ 和 $$$y$$$ 的最大公约数)。从 $$$(1, 1)$$$ 到 $$$(n, n)$$$ 的路线成本是访问过的单元格(包括起始单元格和结束单元格)的成本总和。

找到成本可能最小的路线并打印其成本。

输入

唯一的一行包含三个整数 $$$n$$$、$$$a$$$ 和 $$$b$$$ ($$$2 \le n \le 10^6$$$; $$$1 \le a, b \le 10^6$$$)。

输出

打印一个整数 — 从 $$$(1, 1)$$$ 到 $$$(n, n)$$$ 的最便宜路线的成本。

示例

输入 #1

4 2 4

输出 #1

21

输入 #2

10 210 420

输出 #2

125

注意

第一个示例如上图所示。