\begin{aligned}\sum\limits_{i=1}^nk \bmod i&=\sum\limits_{i=1}^n\left(k-i \times \left\lfloor\frac k i\right\rfloor\right)\\&=\sum\limits_{i=1}^nk-\sum\limits_{i=1}^n \left(i \times \left\lfloor\frac k i\right\rfloor\right)\\&=n \times k-\sum\limits_{i=1}^n \left(i \times \left\lfloor\frac k i\right\rfloor\right)\end{aligned}
求和式直接用整除分块（貌似叫数论分块也可以？）处理，\mathcal O(\sqrt n)。
数论分块的细节：
数论分块的经典问题是求：
\sum\limits_{i=1}^n \left\lfloor\frac n i\right\rfloor
$$\begin{aligned}\left\lfloor\frac n L\right\rfloor&=\left\lfloor\frac n R \right\rfloor\\\left\lfloor\frac n L\right\rfloor&\le \frac n R\\R& \le \left\lfloor\frac{n}{\left\lfloor\frac n L\right\rfloor}\right\rfloor\end{aligned}$$
然后只要从 $1$ 开始枚举，然后以 $1$ 为左界 $L_1$ 算出右界 $R_1$，然后以 $R_1+1$ 为第二个左界 $L_2$，以此类推，直到算到 $R_k=n$。