$$ \begin{aligned} \sum_{i=1}^{n} lcm(i,n) &=n\sum_{d|n}i\sum_{i=1}^{\frac{n}{d}}[gcd(\frac{n}{d},i)=1]\\\\ &=n\sum_{d|n}i\sum_{i=1}^{d}[gcd(d,i)=1]\\\\ &=n\sum_{d|n}i\sum_{i=1}^d\sum_{j|gcd(d,i)}\mu(j)\\\\ &=n\sum_{d|n}\sum_{j|d}\mu(j)\sum_{i=1}^di[j|i]\\\\ &=n\sum_{d|n}\sum_{j|d}\mu(j)j\sum_{i=1}^{\frac dj}i\\\\ &=n\sum_{d|n}\sum_{j|d}\mu(\frac dj)\frac dj\frac{j(j+1)}{2}\\\\ &=\frac n2\sum_{d|n}d\sum_{j|d}j\mu(\frac dj)\\\\ &=\frac n2\sum_{d|n}d\varphi(d) \end{aligned} $$
这里最后推出了dirichelet卷积的形式后面可以根据
$$ \varphi=id_1*\mu $$
直接推出最后的公式