由于是单组数据，强行不分块O(n)过
线性筛部分非常神奇，用了一个奇妙的推导（懒得写了）
1 #include <bits/stdc++.h>
2 using namespace std;
3 int n,m,mu[10000001],f[10000001],p[10000001];bool o[10000001];
4 int main()
5 {
6 scanf("%d",&n);
7 mu[1]=1;
8 for(int i=2;i<=n;i++)
9 {
10 if(!o[i]) p[++m]=i,mu[i]=-1,f[i]=1;
11 for(int j=1;j<=m;j++)
12 if((long long)p[j]*i<=(long long)n)
13 {
14 o[p[j]*i]=1;
15 if(i%p[j]==0) f[p[j]*i]=mu[i];
16 else f[p[j]*i]=mu[i]-f[i];
17 if(i%p[j]==0) break;
18 mu[i*p[j]]=-mu[i];
19 }
20 else break;
21 }
22 long long ret=0;
23 for(int i=1;i<=n;i++)
24 ret+=(long long)(n/i)*(n/i)*f[i];
25 printf("%lld\n",ret);
26 return 0;
27 }