带输入值的莫反解法

8.16杭二的莫反题没有推出来

求\(\sum_{i=1}^n\sum_{j=1}^nlcm(a_i,a_j)\)

解法：同机房奆佬非出题人解法 不过吊打出题人

\[ \begin{align} &\sum_{i=1}^n\sum_{j=1}^nlcm(a_i,a_j)\&=\sum_{i=1}^n\sum_{j=1}^n\frac{a_i\times a_j}{gcd(a_i,a_j)}\&=\sum_{d=1}\sum_{i=1}^n\sum_{j=1}^n\frac{a_i\times a_j}{d}[d=gcd(a_i,a_j)]\&=\sum_{d=1}\sum_{d|a_i}\sum_{d|a_j}\frac{a_i\times a_j}{d}[1=gcd(\frac{a_i}{d},\frac{a_j}{d})]\&=\sum_{d=1}\sum_{d|a_i}\sum_{d|a_j}\frac{a_i\times a_j}{d}\sum_{k=1}\mu(k)[k|gcd(\frac{a_i}{d},\frac{a_j}{d})]\&=\sum_{d=1}\sum_{k=1}\mu(k)\sum_{dk|a_i}\sum_{dk|a_j}\frac{a_i\times a_j}{d}\&=\sum_{T=1}\sum_{k|T}\mu(k)\sum_{T|a_i}\sum_{T|a_j}k\frac{a_i\times a_j}{T}\&=\sum_{T=1}^{max\{a_i\}}\sum_{k|T}k\times \mu(k)\sum_{T|a_i}\sum_{T|a_j}\frac{a_i\times a_j}{T}\\end{align} \]

原文：https://www.cnblogs.com/MYsBlogs/p/11364497.html