```cpp
// 初步思路:求1~n中每一个质数对答案的贡献
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e7 + 50;
const int M = 1e6 + 50;
int phi[N];
bool st[N];
int p[M];
int cnt;
ll sum[N];
void oular(int n) {
phi[1] = 1;
for (int i = 2;i <= n; i++) {
if (!st[i]) {
p[++cnt] = i;//这里qwq
phi[i] = i - 1; // i为质数那么1~i-1均与i互质
}
for (int j = 1;j<=cnt&&p[j] * i<= n ; j++) {//这里 qwq
st[p[j] * i] = true;
// i和p[j]分解质因数的结果相同
// phi[i] = i*(1-1/q1)*(1-1/q2)*....
// phi[i*p[j]] = pj*i*(1-1/q1)*(1-1/q2)...
// phi[i*p[j]] = p[j] * phi[i]
if (i % p[j] == 0) { // i为p[j]的最小质因子
phi[p[j] * i] = p[j] * phi[i];
break;
}
// 欧拉函数为一个积性函数,n = p1*p2...pn,p1~pn互质
//那么phi(n) = phi(p1)*phi(p2)...*phi(pn)
else phi[p[j] * i] = (p[j] - 1 ) * phi[i]; // = phi[p[j]] * phi[i]
}
}
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n; cin >> n;
oular(n);
ll ans = 0;
for (int i = 1;i <= cnt; i++) {
sum[i] = sum[i - 1] + phi[i];
}
for (int i = 1;i <= cnt; i++) {
ans += 2 * sum[n / p[i]] - 1;//这里qwq
}
cout << ans << '\n';
return 0;
}
```
by zyh0516_lucky @ 2023-10-16 23:25:57
@[2022zhangyuanhao](/user/746930) 谢谢lao(^-^)
by xiaobu_dean @ 2023-10-17 09:32:54
@[Dean_code](/user/959579) 这回复时间,应该不是初中,是已经进了高中信竞班的dalao啊,每天上学都在搞信
竞,是吧,您才是lao%%%orz
by zyh0516_lucky @ 2023-10-17 11:57:46
@[2022zhangyuanhao](/user/746930) hhh我是大学生,这回复时间是因为刚起来,您才是lao,orz
by xiaobu_dean @ 2023-10-17 12:48:34
@[Dean_code](/user/959579) 。。。。。。
by zyh0516_lucky @ 2023-10-17 13:17:35