题意:在\([1,A],[1,B]\)中选取一个\(i\)一个\(j\),求\(gcd(i,j)\)不被\(n^2\)整除的\(lcm(i,j)\)的和。
莫比乌斯反演:
\[\begin{aligned} Ans & = \sum_{i=1}^A{\sum_{j=1}^{B}\mu(gcd(i,j))*lcm(i,j)}\\ & = \sum_{d|i,d|j}{\mu^2(d)\sum_{i=1}^A{\sum_{j=1}^B{\frac{i*j}{d}*[gcd(i,j)=d]}}} \\ &=\sum_{d=1}d*\mu^2(d)\sum_{i=1}^{A/d}{\sum_{j=1}^{B/d}{i*j*[gcd(i,j]=1}}\\ &=\sum_d\mu^2(d)*d*l^2{\sum_{l=1}\mu(l)(\sum_{i=1}^{A/(d*l)}i)(\sum_{j=1}^{B/(d*l)}j)}\\ &\because (T=d*l)\\ &=\sum_TF(\frac{A}{T})F(\frac{B}{T})\sum_{d|T}\mu^2(d)*d*\mu(\frac{T}{d})*(\frac{T}{d})^2\\ \end{aligned}\]代码:不会!!