ACM中的很多算法算到最后才发现考得都是数学知识，如果对数学知识掌握的不够深，可能会成为限制你的瓶颈，所以对于数学务必做到：Never too late to learn。
有一个n个节点的图，节点i和节点j之间有长度为1的连边当且仅当gcd(i,j)≠1。
设dis(u,v)表示u到v的最短路，若u不能到达v则dis(u,v)=0,否则dis(u,v)=1。求 n<=10^7 ，求\(\sum_{u<v}dis(u,v)\)
| Time Limit | $1$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $1$ | 正确数量 | $1$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 |
ACM中的很多算法算到最后才发现考得都是数学知识，如果对数学知识掌握的不够深，可能会成为限制你的瓶颈，所以对于数学务必做到：Never too late to learn。
有一个n个节点的图，节点i和节点j之间有长度为1的连边当且仅当gcd(i,j)≠1。
设dis(u,v)表示u到v的最短路，若u不能到达v则dis(u,v)=0,否则dis(u,v)=1。求 n<=10^7 ，求\(\sum_{u<v}dis(u,v)\)
输入一个整数n (1 ≤ n ≤ 107).
打印出dis(u,v)的累加和，即\(\sum_{u<v}dis(u,v)\)的结果，其中1 ≤ u < v ≤ n.
6
8
2 -> 6 -> 3
2 -> 6 -> 4
2 -> 6
3 -> 6 -> 4
3 -> 6
4 -> 6
最终结果为2 + 1 + 1 + 2 + 1 + 1 = 8.
| 本题记录 | 用 户（点击查看用户） | 运行号（点击购买题解） | 时 间 |
|---|---|---|---|
| 算法最快[$766 $ms] | 计爱玲 | 418665 | 2019-05-07 14:54:07 |
| 内存最少[$168036 $KB] | 计爱玲 | 418665 | 2019-05-07 14:54:07 |
| 第一AC | 计爱玲 | 418665 | 2019-05-07 14:54:07 |
| 第一挑战 | 计爱玲 | 418665 | 2019-05-07 14:54:07 |
| 竞赛编号 | 竞赛名称 | 竞赛时间 | 访问比赛 |
|---|