1, CF 870F Paths
大意: n节点图, 节点$x,y$之间有一条边当且仅当$gcd(x,y)!=1$.
求$\sum\limits_{u=1}^n\sum\limits_{v=u+1}^n d(u,v)$, $d$为最短路数组, 不连通时为0.
观察一下可以发现节点1和大于n/2的素数一定是孤立点.
再考虑其余的点对$(x,y)$, 假设$p_x,p_y$为$x,y$的最小素因子
若$d(x,y)=1$, 有$gcd(x,y)>1$
若$d(x,y)=2$, 有$gcd(x,y)=1$且$xy<=n$
若$d(x,y)=3$, 有$gcd(x,y)=1$且$xy>n$且$p_xp_y<=n$
大于三的情况显然不存在, 分别对这三类点计数即可.
原文：https://www.cnblogs.com/uid001/p/10629206.html