GCD SUM
求
[sum_{i=1}^nsum_{j=1}^ngcd(i,j)
]
将原式变换得到
[sum_{d=1}^ndsum_{i=1}^{lfloorfrac{n}{d}
floor}sum_{j=1}^{lfloorfrac{n}{d}
floor}[gcd(i,j)=1]
]
别着急莫比乌斯反演，我们知道
[varphi(n)=sum_{i=1}^n[gcd(i,n)=1]
]
所以原式可化为
[sum_{d=1}^ndsum_{i=1}^{lfloorfrac{n}{d}
floor}（2*varphi(i)-1）
]
这里减一是因为会算重。对于上式，数论分块一下即可根号求。但实际上(varphi)还是要线性求。所以线性的也行。
然而，若是数据太大的话只能根号那就杜教筛加数论分块吧。