题意:

给定很多个数(100000以内个100000以内的数),求选出三个数使其要么两两互质,要么两两不互质,的方案数。

分析:

如果用一条红边连接互质的数,黑边连接不互质的数。那么我们就要求单色三角形的数目。这样的问题往往可以通过补集转化转化为求双色三角形的数目,再用三角形总数减去双色三角形数目得到答案。现在我们发现在1E5的数据范围内你没办法枚举每个三角形,甚至连每一条边的时间都是不够的。

所以我们可以考虑枚举每个三角形的某个顶点,再看它连出的黑边数a和红边数b,那么以它为一个顶点的双色三角形数就是(a*b)。那么所有双色三角形数就是(每个三角形枚举了两次)

$$\frac{1}{2}\sum{a_ib_i}$$

那么现在问题转化为了:如何高效地求每个点连出的红边和黑边数。也就是说如何快速获得与每个数互质与不互质的数的个数。

我们发现求与一个数不互质的数的个数是更方便的。所以拿n减去不互质的数的个数再减1就是互质的数的个数。

现在一个恶心的问题已经转化为了很简单的问题:如何快速求与每个数不互质的数的个数。

解决:

先证明一个引理:1E5以内的数至多有6个质因子。因为2×3×5×7×13×17×19>1E5。那么我们只需要知道每个数的质因子,以及有多少数拥有特定的因子。那么我们可以用容斥原理在64n的时间复杂度内求出这个问题的答案。这件事我们可以在O(nlnn)内预处理出。那么这件事就解决了。