What approach should I adopt for computing the following problem fast?
$$f(n) = \sum_{i=1}^n (n \mod i)$$ $$ 1\le n \le 10^{10}$$
Since the answer can be huge I have to output it modulo some given number m.
$$ 1\le m \le 10^{5}$$
Note that, a fast method to compute the above will suffice, and a closed form expression may not be necessary.
Hint: Start at $i=n$, and go backwards towards $0$. What is the remainder of n when divided by n, $n-1$, $n-2$, etc. ? At what value of i, relative to n, does this behaviour stop ? What formula could we use to directly compute the afore-mentioned partial sum ? Using the above insight, how can the remaining interval be partitioned or subdivided ?