SPOJ5971 LCMSUM - LCM Sum

https://www.spoj.com/problems/LCMSUM/

\[\begin{aligned} ans&=\sum_{i=1}^nlcm(i,n) \\ &=\sum_{i=1}^n \frac{i*n}{gcd(i,n)} \\ &=\sum_{d=1}^n\sum_{i=1}^n[gcd(i,n)=d]\frac{i*n}{gcd(i,n)} \\ &=\sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}[gcd(i,\frac{n}{d})=1] i*n \\ &=n*\sum_{d=1}^n\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}[gcd(i,\frac{n}{d})=1] i \\ &=n*\sum_{d=1}^n\sum_{i=1}^d[gcd(i,d)=1] i \\ \end{aligned} \]

令

\[f(i)=\sum_{i=1}^d[gcd(i,d)=1]i \]

则

\[ans=n*\sum_{d=1}^nf(d) \]

如果我们求出了所有的\(f(d)\)，那么枚举d，让d，2d，3d……kd 都加上这个\(f(d)\)，最后各自再乘上自己，就算完了。这个复杂度是\(nlog_2n\)

\(f(i)\)怎么算？

我们发现\(f(i)\)就是所有与小于等于\(i\)且与\(i\)互质的数的和

\(f(1)=1\)

当\(i>1\)时，\(f(i)=\phi(i)*i/2\)，因为\(gcd(j,i)=gcd(i-j,i)\)，即与\(i\)互质的数成对出现，且每一对相加等于\(i\)

作者：xxy

本文版权归作者所有，转载请用链接，请勿原文转载，Thanks♪(･ω･)ﾉ。