{"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 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_.\n\nThe _gcd_ (greatest common divisor) of two positive integers is the maximum positive integer that divides both of the integers.\n\n## Input\n\nSingle integer _n_ (1 ≤ _n_ ≤ 107).\n\n## Output\n\nPrint the sum of _d_(_u_, _v_) over all 1 ≤ _u_ < _v_ ≤ _n_.\n\n[samples]\n\n## Note\n\nAll shortest paths in the first example:\n\nThere are no paths between other pairs of vertices.\n\nThe total distance is 2 + 1 + 1 + 2 + 1 + 1 = 8.","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)$ 之和。\\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$。\"}]","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\nLet $ 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.\n\n**Constraints**  \n$ 1 \\leq n \\leq 10^7 $\n\n**Objective**  \nCompute:  \n$$\n\\sum_{1 \\leq u < v \\leq n} d(u, v)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF871D","tags":["number theory","sortings"],"sample_group":[["6","8"],["10","44"]],"created_at":"2026-03-03 11:00:39"}}