大概是 $\phi$ 有问题
by ForgotDream_CHN @ 2023-03-31 18:22:14
@[rainygame](/user/804607) 欧拉筛炸了
by VitrelosTia @ 2023-03-31 18:23:58
[过了](https://www.luogu.com.cn/record/106514158)
by ForgotDream_CHN @ 2023-03-31 18:26:06
@[rainygame](/user/804607)
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7+5;
#define int long long
int n;
int phi[maxn];
vector<int> prime;
bool vis[maxn];
long long ans;
long long sum[maxn];
void oula(){
phi[1]=1;
for(int i=2; i<=n; i++){
if (!vis[i]){
prime.push_back(i);
phi[i] = i-1;
}
for (int j: prime){
if (i*j <= n){
vis[i*j] = true;
phi[i*j] = phi[i]*phi[j];
if (i % j == 0) {
phi[i * j] = phi[i] * j;
break;
}
}else{
break;
}
}
}
}
signed main(){
cin >> n;
oula();
for (int i=1; i<=n; i++) sum[i] = sum[i-1] + phi[i];
// for (int i=1; i<=n; i++) cout << phi[i] << ' ';
// cout << '\n';
// for (int i: prime) cout << i << ' ';
// cout << '\n';
// for (int i=1; i<=n; i++) cout << vis[i] << ' ';
// cout << '\n';
for (int i: prime) ans += (sum[n/i]<<1)-1;
cout << ans;
return 0;
}
```
$\phi$ 求错了
by ForgotDream_CHN @ 2023-03-31 18:26:46
@[ForgotDream_CHN](/user/750067) @[VT_SODC3DC3BSLF](/user/672333) 已关
by rainygame @ 2023-03-31 18:45:42