Codeforces Round 440
D Paths
题目大意：给你一个有 \(n\) 个结点的无向图，两个结点 \(u,v\) 之间有边当且仅当 \(gcd(u,v)\neq 1\) ，求所有 \(1\le u<v\le n\) 的 \(dis(u,v)\) 之和，定义 \(u,v\) 不连通时 \(dis(u,v)=0\) 。
题解：记 \(\min[x]\) 为 \(x\) 的最小质因子，显然有：
- \(u = 1\) 或 \(2\min[u] > n\) 或 \(v = 1\) 或 \(2\min[v] > n\) 时， \(dis(u,v)=0\)
- \(gcd(u,v)\neq1\) 时， \(dis(u,v)=1\)
- \(gcd(u,v)=1\) 且 \(\min[u]\cdot\min[v]\le n\) 时， \(dis(u,v)=2\)
- 其它情况下 \(dis(u,v)=3\)
设大于 \(\frac{n}{2}\) 的质数的个数为 \(\text{cnt}\) ，则 \(dis=0\) 的点对有 \((\text{cnt}+1)(n-\text{cnt}-1)\) 个。
\(dis=1\) 的点对有 \({n\choose 2}-\sum_{i=2}^{n}\varphi(i)\) 个。
对于 \(dis=2\) 的点对，我们先不考虑 \(gcd\) 、不考虑 \(u<v\) 计算答案，然后再把 \(gcd\) 大于 \(1\) 的点对去掉，最后除以 \(2\) 即可。对于一个质数 \(p\) ，我们设 \(\text{cnt}'[p]\) 表示 \(1\sim n\) 中最小质因子为 \(p\) 的数的个数，这可以用线性筛预处理。那么不考虑 \(gcd\) 时， \(dis=2\) 的答案为 \(\sum_{p_{1}=2}^{maxp}\sum_{p_{2}=2}^{maxp}[p_{1}p_{2}\le n]\text{cnt}'[p_{1}]\text{cnt}'[p_{2}]\) ，由于所有乘起来小于等于 \(n\) 的 \(p_{1}p_{2}\) 在 \(\mathcal{O}(n)\) 级别，所以我们可以直接暴力枚举所有的 \(p_{1},p_{2}\)。然后我们再考虑去掉 \(gcd\) 大于 \(1\) 的点对，我们枚举所有 \(2\sim n\) 作为 \(u,v\) 的公因子 ，计算这种情况下有多少点对要被去掉，然后再容斥一下去重，得到每个数作为 \(gcd\) 时要去掉的数量 。假设枚举到了 \(k\) ，对于所有 \(\min^{2}[k]\le n\) 的 \(k\) ，以它为公因子的 \(u,v\) 显然刚刚都被计算了，所以以这些数为公因子的点对都应该被去掉。这样我们就只需要考虑所有平方大于 \(n\) 的质数。假如 \(u,v\) 都不是 \(k\) ，那么它们各自的 \(\min\) 一定都小于 \(\sqrt{n}\) ，它们也都应该被去掉。所以不应该被去掉的点对中至少有一个是 \(k\) ，这时数据范围已经很小，我们可以暴力枚举另外一个数来判断。枚举完后我们通过容斥去重，用所有 \(2\sim n\) 的答案去减刚刚得到的答案，再把减完之后的答案除以 \(2\) 即可。
\(dis=3\) 的点对数可以用总的点对数减去其它情况的点对数得到。
