题意：给定 \(n\) 求 \(\displaystyle{\sum_{i=1}^n{\sum_{j=1}^n{\left[(i,j)\in prime\right]}}}\)
其中 \(prime\) 为素数集合。 \(n < 10^7\)
解：原式等于
\[\displaystyle{\sum_{p\in prime}\sum_{i=1}^n{\sum_{j=1}^n{\left[(i,j)=p\right]}}} \]这等于
\[\displaystyle{\sum_{p\in prime}\sum_{i=1}^{\lfloor \frac{n}{p}\rfloor}{\sum_{j=1}^{\lfloor \frac{n}{p}\rfloor}{\left[(i,j)=1\right]}}} \]由于 \((i,j)\) 与 \((j, i)\) 都要被计入总数，我们可以这样
\[\displaystyle{\sum_{p\in prime}\left(\big(\sum_{i=1}^{\lfloor \frac{n}{p}\rfloor}{2\times\sum_{j=1}^{i}{\left[(i,j)=1\right]}\big)-1}\right)} \](这里减 \(1\) 是减到 \(i=j\) 的情况)
我们观察上面的式子，发现可以用 \(\phi\) 函数改写：
\[\displaystyle{\sum_{p\in prime}\left(2\times\sum_{i=1}^{\lfloor \frac{n}{p}\rfloor}{\phi(i)}-1\right)} \]运用线性筛预处理 \(phi\) 前缀和即可做到 \(\mathcal{O(n)}\)
代码：
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1e7 + 10;
int n;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
vector<int> prime(max(n + 1, (int)1e6));
vector<bool> vis(n + 1);
vector<LL> sum(n + 1);
vector<int> phi(n + 1);
int tot = 0;
auto init = [&] {
vis[0] = vis[1] = 1;
phi[1] = 1;
for (int i = 2; i <= n; i++) {
if (!vis[i]) prime[tot++] = i, phi[i] = i - 1;
for (int j = 0; j < tot and prime[j] * i <= n; j++) {
vis[prime[j] * i] = 1;
if (i % prime[j] == 0) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + phi[i];
}
};
init();
LL ans = 0;
for (int i = 0; i < tot; i++) {
ans += 2 * sum[n / prime[i]] - 1;
}
cout << ans << "\n";
return 0;
}