GCD SUM
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
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\)还是要线性求。所以线性的也行。
然而，若是数据太大的话只能根号那就杜教筛加数论分块吧。
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |