GCD SUM

GCD SUM

\[\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j) \]

将原式变换得到

\[\sum_{d=1}^nd\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}[\gcd(i,j)=1] \]

别着急莫比乌斯反演,我们知道

\[\varphi(n)=\sum_{i=1}^n[\gcd(i,n)=1] \]

所以原式可化为

\[\sum_{d=1}^nd\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}(2*\varphi(i)-1) \]

这里减一是因为会算重。对于上式,数论分块一下即可根号求。但实际上\(\varphi\)还是要线性求。所以线性的也行。

然而,若是数据太大的话只能根号那就杜教筛加数论分块吧。

上一篇:题解[SDOI2014]数表


下一篇:洛谷 P3768 简单的数学题