description
给定长度为 \(n\) 的数组 \(c\)。求公因数都不在数组里的有序元素对 \((c_i,c_j),i<j\) 的个数。
\(n\leq 10^6\) ，值域 \(n\)
solution
不妨先计算存在公因数且是无序对且允许 \(i=j\) 的个数，最后容斥一下。
设数组里有 \(a_i\) 个 \(i\)，\(b_i\) 表示 \(i\) 的因数是否在数组中出现过。
则我们要计算的就是 \(\sum\limits_{i=1}^n\sum\limits_{j=1}^n a_{i}a_{j}b_{\gcd(i,j)}\)。
\(\begin{aligned}&\sum\limits_{i=1}^n\sum\limits_{j=1}^n a_{i}a_{j}b_{\gcd(i,j)}\\ &=\sum\limits_{d=1}^nb_d\sum\limits_{i=1}^n\sum\limits_{j=1}^n a_{i}a_{j}[\gcd(i,j)=d] \\&=\sum\limits_{d=1}^nb_d\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n}{d}\rfloor} a_{id}a_{jd}[\gcd(i,j)=1] \\ &=\sum\limits_{d=1}^n b_d \sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n}{d}\rfloor} a_{id}a_{jd} \sum\limits_{p\mid \gcd(i,j)} \mu (p)\end{aligned}\)
设 \(s_{i}=\sum\limits_{j=1}^{\lfloor\frac{n}{i}\rfloor}a_i\)。
那么
\(\begin{aligned}& \sum\limits_{d=1}^n b_d \sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n}{d}\rfloor} a_{id}a_{jd} \sum\limits_{p\mid \gcd(i,j)} \mu (p)\\ &= \sum\limits_{d=1}b_d \sum\limits_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p) s_{dp}^2 \end{aligned}\)
\(a,b,s\) 数组可以 \(O(n\ln n)\) 处理出来，这个式子也可以 \(O(n\ln n)\) 算。
code
Submission #229178122 - Codeforces
标签：lfloor,CF1884D,frac,gcd,limits,sum,rfloor From： https://www.cnblogs.com/FreshOrange/p/17787607.html