前情提要：P2398 GCD SUM 降绿了。

用一个 $O(n\ln n)$ 的简单容斥，倒过来枚举。

看在这道题有一点细节的份上，就当绿吧。

#include<bits/stdc++.h>
using namespace std;
const int maxn=4e4+10;
int cnt[maxn];
int main(){
	int n;scanf("%d",&n);
    n--;
    if(!n){cout<<"0\n";return 0;}
	for(int i=n;i>=1;i--){
		cnt[i]=(n/i)*(n/i);
		for(int j=i*2;j<=n;j+=i) cnt[i]-=cnt[j];
	}
	printf("%d\n",cnt[1]+2);
	return 0;
}