https://www.51nod.com/Challenge/Problem.html#!#problemId=1363
求\(\sum\limits_{i=1}^{n}lcm(i,n)\)
先换成gcd：
\(\sum\limits_{i=1}^{n}\frac{i*n}{gcd(i,n)}\)
显而易见，枚举g：
$ n * \sum\limits_{g|n} \frac{1}{g} \sum\limits_{i=1}^{n} i*[gcd(i,n)==g] $
提g，没有下整符号：
$ n * \sum\limits_{g|n} \frac{1}{g} \sum\limits_{i=1}^{\frac{n}{g}} i*[gcd(i,\frac{n}{g})==1] $
考虑子问题：
$\sum\limits_{i=1}^{n} i*[gcd(i,n)==1] $
也就是n以内和n互质的数的和。
显然可以枚举因数d把他们减掉：
$\sum\limits_{i=1}^{n} i + \sum\limits_{d|n}\mu(d)(d+2d+3d+...+n) $
比如求36的互质数的和时，6在枚举2和枚举3的时候算重，要加回去，4在枚举2的时候算过，不用算。
化简：
$\sum\limits_{i=1}^{n} i + \sum\limits_{d|n}\mu(d)d(1+2+3+...+\frac{n}{d}) $
$\frac{n(n+1)}{2} + \sum\limits_{d|n}\mu(d)d\frac{(1+\frac{n}{d})*\frac{n}{d}}{2} $
原文：https://www.cnblogs.com/Yinku/p/10987912.html