Mod Sum

$A \% B = A - \lfloor A / B \rfloor \times B$ であることを利用すると

$S = \sum^{N}_{k=1}(X - \lfloor X / k \rfloor \times k)$

$\; \; \,\, = XN - \sum^{N}_{k=1}(\lfloor X / k \rfloor \times k)$

$\; \; \,\, = XN - \sum^{X }_{i=1}i \times (N以下かつXを割った時の商がiである自然数の和)$

となります.

また, $X$ を自然数で割った時の商は高々 $2 \sqrt X + 1$ 種類です.

証明:

$1$ 以上 $\sqrt X$ 以下の自然数で $X$ を割ったときの商は$\sqrt X$ 種類, $\sqrt X$ より大きい自然数で割った時の商は0以上 $\sqrt X$ 未満であり高々$\sqrt X + 1$ 種類で, 合わせて $2 \sqrt X + 1$ 種類以下になります.

よって, 商としてあり得る数に対して上記の式を計算すると $O(\sqrt X)$ (または, $O(min(\sqrt X, N))$)で解くことができます.