个人思路：
答案 \(=\) 随便请三个人方案 \(-\) 不合法的方案，考虑计算不合法方案数。
我们将 \(a\) 从小到大排序，对于一对不互质的 \(a_i,a_j \ (i<j)\)，它的贡献为 \(j - i - 1\)。以 \(a_j\) 为最高时，贡献为 \(\sum\limits_{i < j \land gcd(a_i,a_j)>1} (j - i - 1)\)。式子拆开得到 \(j \times k - sum - k\)，其中 \(k\) 为满足 \(i<j\land gcd(a_i,a_j)>1\) 的 \(i\) 的数量，\(sum\) 为这些 \(i\) 的和。
需要快速找到对于一个数 \(a_j\)，所有比它小且不互质的数的数量 \(k\) 与这些数位置 \(i\) 的和 \(sum\)。
我们从前往后遍历，开个桶，记录质因数分解后，第一个质因数为 \(p\) 的数的个数与位置的和。枚举 \(a_j\) 的所有质因数，把对应位置的桶加起来，即可求出 \(k\) 和 \(sum\)。
我们的桶只开 \(\lceil \sqrt{3\times 10^5} \rceil\)。因为值域为 \(3\times 10^5\)，每个数至多含一个超过 \(\sqrt{3\times 10^5}\) 的质因数 \(p\)，我们再开一个桶，记录值为 \(x\) 的 \(a_t\) 的数量，暴力枚举 \(p\) 的倍数 \(x\)，把所有 \(x < a_j \land gcd(\frac{x}{p}, \frac{a_i}{p}) = 1\) 的桶加入答案即可。
预处理 \(\sqrt{3\times 10^5}\) 以内的所有 \(\gcd\) 即可。
时间复杂度 \(O(n\sqrt{n}\log_2 n)\)，\(\log\) 是 \(\gcd\) 复杂度。
上述算法假的，需要容斥才能预处理。
（暂未有新的思路）