L. 数学题

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定正整数 $n$ ，计算下式的结果：

$$\sum_{i=1}^{n}\sum_{j=1}^{n}\lfloor\frac{n}{\max(i, j)}\rfloor[i \perp j]$$

其中 $\lfloor x \rfloor$ 表示对 $x$ 下取整； $[i \perp j]$ 表示 $i$ 与 $j$ 是否互素，即当 $\gcd(i, j) = 1$ 时， $[i \perp j]$ 的值为 $1$ ，否则为 $0$ 。

输入一个正整数 $n \ (1 \le n \le 10^9)$ 。

输出一个正整数，表示上式的值。

有 $25$ 个测试点。

对于前 $10$ 个测试点， $1\le n \le 5\times10^3$ 。

对于后 $15$ 个测试点， $1\le n \le 10^9$ 。