CF870F

感觉完全没有 *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();
}

感谢您的支持，我会继续努力的!