← 返回题目列表

Codeforces · 870/F

F. 路径

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

给定一个正整数 n。让我们在顶点 1, 2, ..., n 上构建一个图,使得顶点 u 和 v 之间存在边当且仅当 $${ \mathrm { g c d } } ( u, v ) \neq 1$$。令 d(u, v) 为 u 和 v 之间的最短距离,如果它们之间没有路径,则为 0。计算所有 1 ≤ u < v ≤ n 的值 d(u, v) 之和。

两个正整数的 gcd(最大公约数)是整除这两个整数的最大正整数。

输入

单个整数 n (1 ≤ n ≤ 107)。

输出

打印所有 1 ≤ u < v ≤ n 上 d(u, v) 的总和。

示例

输入 #1

6

输出 #1

8

输入 #2

10

输出 #2

44

注意

第一个示例中的所有最短路径:

- $$2 \右箭头 6 \右箭头 3$$
- $$2 \右箭头 4$$
- $$2 \右箭头 6$$
- $$3 \右箭头 6 \右箭头 4$$
- $$3 \右箭头 6$$
- $$\overrightarrow{4} \to \overrightarrow{6}$$

其他顶点对之间没有路径。

总距离为 2 + 1 + 1 + 2 + 1 + 1 = 8。