首先考虑 (d(u,v)) 是个什么东西，分情况讨论：
- (u otperp v)，(d(u,v)=1)
- (uperp v)，记 (p_u) 为 (u) 的最小质因子，(p_v) 为 (v) 的最小质因子，那么继续分情况讨论：
- (p_up_vle n)，(d(u,v)=2)（(u o p_up_v o v)）
- (p_up_v>n) 且 (max(p_u,p_v)ledfrac{n}{2})，(d(u,v)=3)（(u o 2p_u o 2p_v o v)）
- (p_up_v>n) 且 (max(p_u,p_v)>dfrac{n}{2})，(d(u,v)=0)
考虑对这四种情况分别计算，对于 (d(u,v)=1) 显然预处理出欧拉函数即可处理，即 (dbinom{n-1}{2}-sumlimits_{i=1}^n(varphi(i)-1))（由于 (1) 不能与任何点连边，因此 (d(u,v) e 0) 的点只可能在另外 (n-1) 个点之间），对于 (d(u,v)=2) 的情况直接处理比较困难，因此考虑正难则反，拿总方案数减去另外三种情况的方案数即可计算，对于第三种情况，由于 (p_up_v>0)，因此在 ([1,n]) 中不存在某个数既是 (p_u) 也是 (p_v) 的倍数，因此对于某个固定的 (p_u,p_v)，合法的 (u,v) 的对数即是 ([1,n]) 中 (p_x=p_u) 的 (x) 的个数与 ([1,n]) 中 (p_x=p_v) 的 (x) 的个数之积。我们不妨假设 (p_u<p_v)，我们记 (cnt_x) 表示 ([1,n]) 中有多少个数最小质因子为 (x)，那么考虑枚举 (p_u)，合法的 (p_v) 必然在区间 ((max(p_u,dfrac{n}{p_u}),dfrac{n}{2}]) 之间，前缀和优化一下即可。对于第四种情况也同理，枚举 (p_u)，合法的 (p_v) 在区间 ((max(i,dfrac{n}{2}),n]) 之间。第二种情况减一下即可，复杂度线性。
最后讲一下我翻车的现场，我是考虑求出分别求出 (d(u,v)=1/2/3) 的情况并将它们的贡献加起来，(d(u,v)=1,3) 的情况自然是很容易求得的，但是 (d(u,v)=2) 的情况不好计算，然后我就一直在分析如何计算这种情况的方案数，xtbz……看来以后对于计算方案数的问题，如果正面计算比较困难要学会正难则反，学到了学到了（
const int MAXN=1e7;
int n,pr[MAXN/10+5],prcnt=0,mnp[MAXN+5],phi[MAXN+5],cnt[MAXN+5];
bitset<MAXN+5> vis;
void sieve(){
phi[1]=1;
for(int i=2;i<=n;i++){
if(!vis.test(i)){pr[++prcnt]=i;phi[i]=i-1;mnp[i]=i;}
for(int j=1;pr[j]*i<=n&&j<=prcnt;j++){
vis[pr[j]*i]=1;mnp[pr[j]*i]=pr[j];
if(i%pr[j]==0){phi[pr[j]*i]=phi[i]*pr[j];break;}
else phi[pr[j]*i]=phi[i]*phi[pr[j]];
}
}
}
int calc(int l,int r){return (l>r)?0:(cnt[r]-cnt[l]);}
int main(){
scanf("%d",&n);sieve();ll sum=0,ans0=0,ans1=0,ans2=0,ans3=0;
for(int i=2;i<=n;i++) cnt[mnp[i]]++;
for(int i=1;i<=n;i++) cnt[i]+=cnt[i-1];
for(int i=1;i<=n;i++) sum+=phi[i]-1;
ans1=1ll*(n-1)*(n-2)/2-sum;
for(int i=1;i<=n;i++){
int num=cnt[i]-cnt[i-1];
if(i<=n/2) ans3+=1ll*num*calc(max(i,n/i),n/2);
ans0+=1ll*num*calc(max(n/2,i),n);
} ans2=sum-ans0-ans3;
printf("%lld
",ans1+(ans2<<1)+(ans3<<1)+ans3);
return 0;
}