### 题目描述
求
$$\sum \limits _ {i = 1} ^ n \sum \limits _ {j = 1} ^ n \gcd(i, j)$$
#### 样例
```
输入:
2
输出:
5
```
----------
### 算法1
##### (线性筛) $O(n)$
将式子变形:
要知道一个前置定理
> $\sum \limits _ {d | n} \varphi \( d \) = n$
艾弗森约定:
> 定义 $\\\ [P]$ = $$\begin{cases} P \text{ } is \text { }true \text{ }1 \\\ P \text{ }is \text{ }false \text{ }0 \end{cases}$$
$$\sum \limits _ {i = 1} ^ n \sum \limits _ {j = 1} ^ n \gcd \( i, j\)\\\$$
$$=\sum \limits _ {i = 1} ^ n \sum \limits _ {j = 1} ^ n \sum \limits _ {k | \gcd \( i, j \)} \varphi \( k \)\\\$$
$$=\sum \limits _ {i = 1} ^ n \sum \limits _ {j = 1} ^ n \sum \limits _ {k | i, k | j} \varphi \( k \)\\\$$
$$=\sum \limits _ {k = 1} ^ n \varphi \( k \) \sum \limits _ {i = 1} ^ n \sum \limits _ {j = 1} ^ n [k | i][k | j]$$
$$=\sum \limits _ {k = 1} ^ n \varphi \( k \) \lfloor \frac {n}{k} \rfloor \lfloor \frac {n}{k} \rfloor$$
就可以$O(n)$预处理欧拉函数然后$O(\sqrt n)$数论分块过掉了
#### C++ 代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1e5 + 5; typedef long long LL; int n; int primes[N], cnt; LL phi[N], sum[N]; bool st[N]; void init(int n) { phi[1] = 1; for (int i = 2; i <= n; i ++ ) { if (!st[i]) { primes[cnt ++ ] = i; phi[i] = i - 1; } for (int j = 0; primes[j] <= n / i; j ++ ) { st[primes[j] * i] = true; if (i % primes[j] == 0) { phi[primes[j] * i] = phi[i] * primes[j]; break; } phi[primes[j] * i] = phi[i] * (primes[j] - 1); } } for (int i = 1; i <= n; i ++ ) sum[i] = sum[i - 1] + phi[i]; } int main() { init(N - 1); scanf("%d", &n); LL res = 0; for (int l = 1, r; l <= n; l = r + 1) { r = n / (n / l); res += (sum[r] - sum[l - 1]) * (n / l) * (n / l); } printf("%lld", res); return 0; }