#P1390. 公约数的和

    ID: 434 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数论数学O2优化素数判断质数筛法最大公约数gcd莫比乌斯反演

公约数的和

题目背景

有一天,TIBBAR 和 LXL 比赛谁先算出 1n1 \sim nnn 个数中每任意两个不同的数的最大公约数的和。LXL 还在敲一个复杂而冗长的程序,争取能在 100s100s 内出解。而 TIBBAR 则直接想 1s1s 秒过而获得完胜,请你帮他完成这个任务。

题目描述

给定 nn,求

i=1nj=i+1ngcd(i,j)\sum_{i = 1}^n \sum_{j = i + 1}^n \gcd(i, j)

其中 gcd(i,j)\gcd(i, j) 表示 iijj 的最大公约数。

输入格式

输入只有一行一个整数,表示 nn

输出格式

输出一行一个整数表示答案。

10
67

提示

数据规模与约定

  • 对于 40%40\% 的数据,保证 n2×103n \leq 2 \times 10^3
  • 对于 100%100\% 的数据,保证 2n2×1062 \leq n \leq 2 \times 10^6