D. Paths

Codeforces

IDCF871D

Time4000ms

Memory512MB

Difficulty—

number theorysortings

English · Original

Chinese · Translation

Formal · Original

You are given a positive integer _n_. Let's build a graph on vertices 1, 2, ..., _n_ in such a way that there is an edge between vertices _u_ and _v_ if and only if . Let _d_(_u_, _v_) be the shortest distance between _u_ and _v_, or 0 if there is no path between them. Compute the sum of values _d_(_u_, _v_) over all 1 ≤ _u_ < _v_ ≤ _n_. The _gcd_ (greatest common divisor) of two positive integers is the maximum positive integer that divides both of the integers. ## Input Single integer _n_ (1 ≤ _n_ ≤ 107). ## Output Print the sum of _d_(_u_, _v_) over all 1 ≤ _u_ < _v_ ≤ _n_. [samples] ## Note All shortest paths in the first example: There are no paths between other pairs of vertices. The total distance is 2 + 1 + 1 + 2 + 1 + 1 = 8.

[{"iden":"statement","content":"给定一个正整数 $n$。在顶点 $1, 2, ..., n$ 上构建一个图，使得当且仅当 $\gcd(u, v) > 1$ 时，顶点 $u$ 和 $v$ 之间有一条边。令 $d(u, v)$ 表示 $u$ 和 $v$ 之间的最短距离，若它们之间无路径则为 $0$。计算所有 $1 ≤ u < v ≤ n$ 的 $d(u, v)$ 之和。\n\n两个正整数的最大公约数（$\gcd$）是能同时整除这两个整数的最大正整数。\n\n单个整数 $n$（$1 ≤ n ≤ 10^7$）。\n\n请输出所有 $1 ≤ u < v ≤ n$ 的 $d(u, v)$ 之和。\n\n第一个示例中的所有最短路径：\n\n其他顶点对之间不存在路径。\n\n总距离为 $2 + 1 + 1 + 2 + 1 + 1 = 8$。\n\n"},{"iden":"input","content":"单个整数 $n$（$1 ≤ n ≤ 10^7$）。"},{"iden":"output","content":"请输出所有 $1 ≤ u < v ≤ n$ 的 $d(u, v)$ 之和。"},{"iden":"examples","content":"输入6输出8输入10输出44"},{"iden":"note","content":"第一个示例中的所有最短路径：其他顶点对之间不存在路径。总距离为 $2 + 1 + 1 + 2 + 1 + 1 = 8$。"}]

**Definitions** Let $ n \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 10^7 $. Define a graph $ G = (V, E) $ where $ V = \{1, 2, \dots, n\} $, and $ (u, v) \in E $ if and only if $ \gcd(u, v) > 1 $. Let $ d(u, v) $ denote the shortest path distance between vertices $ u $ and $ v $ in $ G $, with $ d(u, v) = 0 $ if $ u $ and $ v $ are in different connected components. **Constraints** $ 1 \leq n \leq 10^7 $ **Objective** Compute: $$ \sum_{1 \leq u < v \leq n} d(u, v) $$

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "D. Paths",
    "description": {
      "content": "You are given a positive integer _n_. Let's build a graph on vertices 1, 2, ..., _n_ in such a way that there is an edge between vertices _u_ and _v_ if and only if . Let _d_(_u_, _v_) be the shortest",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF871D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a positive integer _n_. Let's build a graph on vertices 1, 2, ..., _n_ in such a way that there is an edge between vertices _u_ and _v_ if and only if . Let _d_(_u_, _v_) be the shortest...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"给定一个正整数 $n$。在顶点 $1, 2, ..., n$ 上构建一个图，使得当且仅当 $\\gcd(u, v) > 1$ 时，顶点 $u$ 和 $v$ 之间有一条边。令 $d(u, v)$ 表示 $u$ 和 $v$ 之间的最短距离，若它们之间无路径则为 $0$。计算所有 $1 ≤ u < v ≤ n$ 的 $d(u, v)$ 之和。...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 10^7 $.  \nDefine a graph $ G = (V, E) $ where $ V = \\{1, 2, \\dots, n\\} $, and $ (u, v) \\in E $ if and only if $ \\gcd(u, v) > 1 $.  \n\nL...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments