先不管最后一个，就变成了这个：
\[
\sum_{i=1}^{n-1}lcm(i,n)
\]
将 \(lcm\) 转化为 \(gcd\)：
\[
Ans=\sum_{i=1}^{n-1}\frac{in}{gcd(i,n)}
\]
转化下，其实没有区别：
\[
Ans=\frac12\cdot 2\sum_{i=1}^{n-1}\frac{in}{gcd(i,n)}
\]
再次转化，倒着求和：
\[
Ans=\frac12\cdot(\sum_{i=1}^{n-1}\frac{in}{gcd(i,n)}+\sum_{i=n-1}^1\frac{in}{gcd(i,n)})
\]
因为 \(gcd(i,n)=gcd(n-i,i)\)
所以：
\[
Ans=\frac12\cdot(\sum_{i=1}^{n-1}\frac{in}{gcd(i,n)}+\sum_{i=n-1}^1\frac{in}{gcd(n-i,n)})
\]
然后我们发现分母相同于是合并：
\[
Ans=\frac12\cdot(\sum_{i=1}^{n-1}\frac{n^2}{gcd(i,n)})
\]
考虑枚举 \(gcd\) ,先算上 \(n\) ：
\[
Ans=\frac12n\cdot\sum_{d|n}\frac{n}{d}\cdot \sum_{i=1}^{n}[gcd(i,n)==d]
\]
继续：
\[
Ans=\frac12n\cdot\sum_{d|n}\frac{n}{d}\cdot \sum_{i=1}^{\frac nd}[gcd(i,n)==1]
\]
发现后面的其实就是 \(\phi(\frac {n}d)\) ：
\[
Ans=\frac12n\cdot\sum_{d|n}\frac{n}{d}\cdot\phi(\frac{n}d)
\]
然后等价于:
\[
Ans=\frac12n\cdot\sum_{d|n}d\cdot\phi(d)
\]
然后把多算的减掉:
\[
Ans=(\frac12n\cdot\sum_{d|n}d\cdot\phi(d))-\frac12n
\]
然后把少算的加回去:
\[
Ans=(\frac12n\cdot\sum_{d|n}d\cdot\phi(d))-\frac12n+n\\
=(\frac12n\cdot\sum_{d|n}d\cdot\phi(d))+\frac12n\\
=\frac12n\cdot((\sum_{d|n}d\cdot\phi(d))+1)
\]
于是就推完了
预处理时间复杂度是 \(O(nlogn)\) 的
但是有一种 \(O(n)\) 的方法,因为数据比较小,没有研究
数论题目真套路