题解 P3911 【最小公倍数之和】

$$ ans=\sum_{i=1}^n\sum_{j=1}^nlcm(A_i,A_j) $$ $$ \begin{aligned} ans & =\sum_{i=1}^n\sum_{j=1}^nlcm(A_i,A_j) \\ & =\sum_{i=1}^n\sum_{j=1}^n\frac{A_i\cdot A_j}{gcd(A_i,A_j)} \\ & =\sum_{i=1}^n\sum_{j=1}^nA_i\cdot A_j\sum_{t=1}^{A_i}\frac{1}{t}[gcd(A_i,A_j)=t] \\ & =\sum_{t=1}^{A_m}\frac{1}{t}\sum_{i=1}^n\sum_{j=1}^nA_i\cdot A_j[gcd(A_i,A_j)=t] \\ & =\sum_{t=1}^{A_m}t\sum_{i=1}^n\sum_{j=1}^n[A_i mod\; t=0][A_j mod\;t=0]\cdot \frac{A_i\cdot A_j}{t^2}[gcd(A_i/t,A_j/t)=1] \\ & =\sum_{t=1}^{A_m}t\sum_{i=1}^n\sum_{j=1}^n[A_i mod\; t=0][A_j mod\;t=0]\cdot \frac{A_i\cdot A_j}{t^2}\sum_{d|gcd(A_i/t,A_j/t)}\mu(d) \end{aligned} $$ ----------------------- 打住，我们这些式子始终都在数组上进行，根本没有脱离数组，这导致我们根本没法进行数论变换 所以我们需要把数组转化到数上去 ------------------- $$ 1\leq N \leq 50000 $$ $$ 1\leq A_i \leq 50000 $$ 我们就可以根据这个式子 $$ \sum_{i=1}^{n}\sum_{j=1}^nlcm(i,j) $$ 我们想想怎么加一个限制才能使答案不重不漏 数量！ 我们记录一个数字x在数列中出现了多少次，记为数组c 所以我们现在要求的是 $$ \begin{aligned} ans= & \sum_{i=1}^n\sum_{j=1}^n lcm(i,j)\times c_i \times c_j\\ =& \sum_{i=1}^n\sum_{j=1}^n \frac{i \times j\times c_i \times c_j}{\gcd(i,j)} \\ =& \sum_{d=1}^n\sum_{i=1}^{\lfloor n/d \rfloor}\sum_{j=1}^{\lfloor n/d \rfloor}[\gcd(i,j)=1]d\times i \times j \times c_{id} \times c_{jd} \\ =& \sum_{d=1}^n\sum_{i=1}^{\lfloor n/d \rfloor}\sum_{j=1}^{\lfloor n/d \rfloor}\sum_{k|\gcd(i,j)}\mu(k) \times d\times i \times j \times c_{id} \times c_{jd} \\ =& \sum_{d=1}^n\sum_{k=1}^{\lfloor n/d\rfloor}\sum_{i=1}^{\lfloor n/kd\rfloor}\sum_{j=1}^{\lfloor n/kd\rfloor}\mu(k)\times d \times i \times j \times k^2 \times c_{idk} \times c_{jdk} \\ =& \sum_{T=1}^{n}T\times(\sum_{i=1}^{\lfloor n/T \rfloor}i\times c_{iT})^2\sum_{k|T}\mu(k)\times k \end{aligned} $$ 那么我们前面的可以进行预处理 时间复杂度 $$ O(n\cdot ln(n)) $$