CF870F Paths

题意：给定一张 个点的图，点编号为 。

对于点 。若 ，则 到 有一条长度为 的无向边。

记 表示从 到 的最短路长度，如果 无法到 ，则 。

求节点两两之间距离之和。

，时限 。

---

对于两个数 ，考虑如何快速求出 。

在判定两个数能不能连边时，只需要考虑质因子集合，不需要考虑质因子次数。

• 若 中有一个为 ，则 ，直接将 忽略。

• 若两个数不互质，则直接连接。（ Case #A ）

• 对于两个互质的数 ，取出各自的最小质因子 。

  若 ，则 ，。（ Case #B ）

  若 且 ，则 。。（ Case #C ）

  若 ，则 。（ Case #D ）

下面对每种情况分别统计贡献。

• Case #A

线性筛即可。

• Case #B

算出互质数对的总数，再减去其他情况。

• Case #C

记 为 的最小质因子。

这里由于 ，故一个数不可能同时含有 （或更大的素因子）。

因此，有 。

预处理

• Case #D

---

总复杂度 。

本题的妙处在于， 四种情况的统计并不是一样难的，需要适当运用正难则反思想。

关键在于 的一步转化。