求 $\displaystyle\sum_{i=1}^n \operatorname{lcm}(i,n)$
容易想到，原式可以化为 $\displaystyle n \sum_{i=1}^n\dfrac{i}{\gcd(i,n)}$
类似 P2303的做法 ，$\gcd(i,n)$ 可以化为 $\displaystyle\sum_{d \mid n}d[\gcd(i,n)=d]$
所以就得到了 $\displaystyle n \sum{i=1}^n $ $\sum{d \mid n} \dfrac{i}{d[\gcd(i,n)=d]}$
略微整理，得到 $\displaystyle n\sum{d \mid n} $ $\sum{i=1}^{n}\dfrac{i}{d}[\gcd(i,n)=d]$
显然，对答案有贡献的 $i$ 一定是 $d$ 的倍数，即 $i = kd$
于是就得到了 $\displaystyle n \sum{d|n}\sum{k=1}^{kd\leq n}k[\gcd(kd,n)=d]$
整理得 $\displaystyle n \sum{d|n}\sum{k=1}^{\frac{n}{d}}k[\gcd(k,\dfrac{n}{d})=1]$
然后考虑 $\displaystyle\sum_{k=1}^{\frac{n}{d}}k[\gcd(k,\dfrac{n}{d})=1]$ 这一坨的意义：与 $\dfrac{n}{d}$ 互质的所有数的和。
因为 $\gcd(k,\dfrac{n}{d})=\gcd(\dfrac{n}{d},\dfrac{n}{d}-k)$ ，所以 $k$ 是成对出现的，且每一对的 $k$ 的和为 $\dfrac{n}{d}$， 一共有 $\lceil\dfrac{\varphi(\dfrac{n}{d})}{2}\rceil$ 对
所以，$\displaystyle\sum_{k=1}^{\frac{n}{d}}k[\gcd(k,\dfrac{n}{d})=1]=\lceil\dfrac{\varphi(\dfrac{n}{d})}{2}\rceil\times d$
因此，原式可以被整理为 $\displaystyle n\sum_{d|n}d\left\lceil\dfrac{\varphi(\dfrac{n}{d})}{2}\right\rceil$