法1：
-
我们之前肯定看过这样一道非常经典的题：
-
求 \(a_i\) 中有多少对 \((i,j)\)，满足 \(\gcd(a_i,a_j)=1\)
\(n \leq 10^6\)
-
这题是莫反板子题，但显然可以不用莫反做。先不说这题怎么做，我们发现这道题和 CF1884D 的不同之处在于这题 \(\gcd\) 可以为一些特殊的值
-
我们先考虑原题 \(O(n^2)\) 怎么做，我们可以枚举 \((i,j)\)，记录 \(f_i\) 表示 \(a\) 中是否存在 \(i\) 的因子，不存在为 \(1\)，存在为 \(0 \)。
-
则答案为：
- \[\sum_{i=1}^{n}\sum_{j=i+1}^{n} f_{\gcd(a_i,a_j)} \]
-
然后考虑怎么优化成 \(O(n \log n)\)，发现 \(a_i \leq n\)，因此要用到一个非常经典的思路：改变枚举顺序
-
我们改为枚举 \(\gcd(a_i,a_j)\)，则答案变为：
- \[\sum_{g=1}^{n} f_g \times num_g \]
-
其中 \(num_g\) 表示 \(\gcd = g\) 的数对个数。然后求 \(num_g\) 的过程就变成了上面那个问题
-
我们考虑数论容斥：设 \(g_i\) 表示 \(i|gcd(a_x,a_y)\) 的个数，然后再容斥即可
-
复杂度 \(O(n \ln n)\)
法2：
-
我们之前肯定看过这样一道非常经典的题：
-
求 a_i 中有多少对 (i,j)，满足 \gcd(a_i,a_j)=1
n \leq 10^6
-
这题是莫反板子题，因此这题我们也考虑暴力莫反
-
现在是推式子时间！
-
记 \(b_i\) 为 \(a_i\) 的桶
- \[\begin{align} \sum_{i=1}^{n}\sum_{j=i+1}^{n} \prod_{k|a_i,k|a_j} [b_k=0] &= \sum_{i=1}^{n}\sum_{j=i+1}^{n} \prod_{k|a_i,k|a_j} [b_k=0] \end{align} \]
-
然后转为枚举实际的值，而不是编号
- \[\begin{align} \sum_{i=1}^{n}\sum_{j=1}^{n} b_i b_j f_{\gcd(i,j)} &= \sum_{i=1}^{n}\sum_{j=1}^{n} \sum_{d=1}^{n} b_i b_j f_d [\gcd(i,j)=d] \\ &= \sum_{d=1}^{n} \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{n}{d} \rfloor} b_{id} b_{jd} f_d [\gcd(i,j)=1] \\ &= \sum_{d=1}^{n} \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{n}{d} \rfloor} b_{id} b_{jd} f_d \sum_{k|i,k|j} \mu(k) \\ &= \sum_{d=1}^{n} f_d \sum_{k=1}^{\lfloor \frac{n}{d} \rfloor} \mu(k) \sum_{i=1}^{\lfloor \frac{n}{dk} \rfloor} \sum_{j=1}^{\lfloor \frac{n}{dk} \rfloor} b_{idk} b_{jdk} \\ &= \sum_{d=1}^{n} f_d \sum_{k=1}^{\lfloor \frac{n}{d} \rfloor} \mu(k) (\sum_{i=1}^{\lfloor \frac{n}{dk} \rfloor} b_{idk})^2 \\ &= \sum_{T=1}^{n} (\sum_{i=1}^{\lfloor \frac{n}{T} \rfloor} b_{iT})^2 \sum_{d|T} f_d \mu(\frac{T}{d}) \end{align} \]
-
此时前面的平方可以 \(O(n \ln n)\) 处理，去除这一项后剩余的是一个狄利克雷卷积的形式，可以做到 \(O(n \ln n)\)，故最终复杂度 \(O(n \ln n)\)
-
注意：这么算的是没有顺序的，但因为 \((i,i)\) 不可能成为答案，要注意答案除以 \(2\)