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♪(･ω･)ﾉ。