感觉完全没有 *2700？
看到题，猜测 \(\max dis\) 不会很大，于是按照路径种类分类讨论一下路径 \((i,j)\)。下设 \(f_i\) 为最小质因数，并且更下面的情况不包括上面的情况。
- \(\gcd(i,j)>1\)
这种显然 \(dis=1\)，数量则为 \(\sum\limits_n(i-1-\varphi(i))\)。
- \(f_i\times f_j\le n\)
这种可以设置一个中转点为 \(f_i\times f_j\)。路径则为 \(i\to f_i\times f_j\to j\)。
考虑怎样计数。发现对于一个 \(i\) 计算有多少个满足条件的 \(j<i\) 且 \((i,j)\) 不满足上面情况是困难的，但是如果不加后两个要求则是简单的，于是先算总数再减去不满足两个要求的。
计算总数可以考虑对于每个质数 \(x\) 找出最大的满足 \(x\times y\le n\) 的质数 \(y\)。并记录一个 \(cnt_i\) 表示有多少个 \(j\) 满足 \(f_j=i\)，再对 \(cnt\) 做一个前缀和，就可以快速计算了。
然后减去 \(i=j\) 和 \(\gcd(i,j)>1\) 的情况就行了。
- \(f_i\le \dfrac{n}{2}\land f_j\le\dfrac{n}{2}\)
思考发现这种的路径即为 \(i\to 2\times f_i\to 2\times f_j\times j\)。理论上来说这种是比较难计数的，但是还是和上一种一样的思路，正难则反。所有满足上述条件的减去满足前两个条件的数量。就可以轻松解决。
需要线性筛预处理，没什么细节，具体可以参考代码。
code：
点击查看代码
int n,m,pm[N],c[N],f[N],g[N],phi[N],h[N],s[N];
bool vis[N];
void Yorushika(){
scanf("%d",&n);
ll sphi=0;
rep(i,2,n){
if(!vis[i]){
pm[++m]=i,c[m]++;
f[i]=i,g[i]=m,phi[i]=i-1;
}
rep(j,1,m){
if(i>n/pm[j])break;
int k=i*pm[j];
vis[k]=1,f[k]=pm[j];
c[g[pm[j]]]++;
if(i%pm[j]==0){phi[k]=phi[i]*pm[j];break;}
phi[k]=phi[i]*(pm[j]-1);
}
sphi+=i-1-phi[i];
}
int j=m;
pm[0]=1;
rep(i,1,m){
while(pm[i]>n/pm[j])j--;
h[i]=j,s[i]=s[i-1]+c[i];
}
ll sum=0,cnt=0;
rep(i,2,n){
sum+=s[h[g[f[i]]]];
sum-=f[i]<=n/f[i];
cnt+=f[i]<=n/2;
}
sum/=2,cnt=cnt*(cnt-1)/2;
printf("%lld\n",(sum-sphi)*2+sphi+(cnt-sum)*3);
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
Yorushika();
}