题解

思路

一对数是否为坏对只取决于它们的最大公约数 $g$：当且仅当数组中存在一个出现过的数整除 $g$，这对数是坏对。

做法

记 $c_x$ 为值 $x$ 的出现次数，$s_d=\sum_{d\mid x}c_x$。那么最大公约数是 $d$ 的倍数的数对共有 $\binom{s_d}{2}$ 对。按 $d$ 从大到小，用

得到最大公约数恰为 $d$ 的数对数。

再从每个出现过的值 $x$ 出发，标记它的所有倍数。未被标记的 $d$ 不含任何出现过的约数，因此把对应的 $e_d$ 加入答案。

全质数子任务中，只有两个数相同才会被该质数同时整除，答案为总数对减去每种质数内部的数对。小规模则可枚举数对及见证元素。

独立复核实现使用莫比乌斯反演：$e_g=\sum_d\mu(d)\binom{s_{gd}}2$。

复杂度

每组时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。