通过/p改变为互质的情况
维护欧拉函数前缀和即可。
GCD - 洛谷
#include<bits/stdc++.h>
using namespace std;
const int N = 1e7+8;
vector<int> pri;
bool not_prime[N];
long long phi[N];
long long sum[N];
void pre(int n) {phi[1] = 1;for (int i = 2; i <= n; i++) {if (!not_prime[i]) {pri.push_back(i);phi[i] = i - 1;}for (int pri_j : pri) {if (i * pri_j > n) break;not_prime[i * pri_j] = true;if (i % pri_j == 0) {phi[i * pri_j] = phi[i] * pri_j;break;}phi[i * pri_j] = phi[i] * phi[pri_j];}}for(int i = 1;i <= n;i++){sum[i] = sum[i-1]+phi[i];}
}
long long ans;
int n;
int main(){cin>>n;pre(n);for (int p: pri ){ans += 2*(sum[n/p])-1;}cout<<ans;return 0;
}