求 \(\displaystyle\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)\)
\(n\leq10^5\)
数论
先常规化式子（大雾
\[\begin{aligned}&\displaystyle\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)\\&=\displaystyle\sum_{k=1}^n\sum_{i=1}^n\sum_{j=1}^n{\ k\times[\gcd(i,j)=k]}\\&=\displaystyle\sum_{k=1}^nk\sum_{i=1}^n\sum_{j=1}^n{[\gcd(i, j)=k]}\\&=\displaystyle\sum_{k=1}^n{k\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}}\sum_{j=1}^{\lfloor\frac{n}{k}\rfloor}{[\gcd(i,j)=1]}\end{aligned}
\]
\]
似乎原问题就转化为了快速求 \(\displaystyle{\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}}\sum_{j=1}^{\lfloor\frac{n}{k}\rfloor}{[\gcd(i,j)=1]}\)
是不是有点 似曾相识
容易发现上式可以用 \(\varphi\) 替代，即 \(2\displaystyle\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\varphi(i)-1\)
因此原式即为 $$\displaystyle\sum_{k=1}n{k (2\displaystyle\sum_{i=1}{\lfloor\frac{n}{k}\rfloor}\varphi(i)-1)}$$
时间复杂度 \(O(n)\) ，也可以用数论分块优化到 \(O(\sqrt n)\)
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
int n, tot, p[maxn]; ll phi[maxn];
void sieve() {
phi[1] = 1;
for (int i = 2; i <= n; i++) {
if (!p[i]) p[++tot] = i, phi[i] = i - 1;
for (int j = 1; j <= tot && i * p[j] <= n; j++) {
p[i * p[j]] = 1;
if (i % p[j] == 0) {
phi[i * p[j]] = phi[i] * p[j]; break;
}
phi[i * p[j]] = phi[i] * phi[p[j]];
}
}
for (int i = 1; i <= n; i++) {
phi[i] += phi[i - 1];
}
}
int main() {
scanf("%d", &n), sieve(); ll ans = 0;
for (int i = 1; i <= n; i++) {
ans += i * (phi[n / i] * 2 - 1);
}
printf("%lld", ans);
return 0;
}