A huge sum

Problem E in the latest atCoder beginner round was quite interesting. The problem statement is quite simple, we are asked to compute

$$\sum_{i=1}^{N}{\lfloor \frac{N}{i} \rfloor}$$

for $1\leq N \leq 10^{12}$.

This problem would be easy if $N$ wasn't so huge. But since it is, we need a faster way to compute the sum than just doing it directly.

The first thing to notice is that all $\lfloor \frac{N}{2}\rfloor < i \leq N$ have $\lfloor \frac{N}{i}\rfloor =1$. More generally, $\lfloor \frac{N}{k+1}\rfloor < i \leq \lfloor \frac{N}{k}\rfloor$ have $\lfloor\frac{N}{i}\rfloor = k$. So our strategy becomes to group equal values together.

If we do this for say $X$ groups we will have 

$$N-((N-\lfloor \frac{N}{2}\rfloor)+(\lfloor \frac{N}{2}\rfloor - \lfloor \frac{N}{3}\rfloor) + ... + (\lfloor \frac{N}{X}\rfloor - \lfloor \frac{N}{X+1}\rfloor))=\lfloor \frac{N}{X+1}\rfloor$$

values of $i$ for which we have still not computed the value of $\lfloor \frac{N}{i}\rfloor$ for. If we choose $X=\lfloor\sqrt{N}\rfloor$, then we have $O(\sqrt{N})$ groups and $\lfloor \frac{N}{\sqrt{N}+1}\rfloor = O(\sqrt{N})$ indices $i$ for which we can directly compute their contribution.

Thus we compute the sum using the following.

$$\sum_{k=1}^{\lfloor\sqrt{N}\rfloor}{k\cdot\left(\lfloor \frac{N}{k}\rfloor - \lfloor \frac{N}{k+1}\rfloor\right)} + \sum_{i=1}^{\lfloor \frac{N}{\sqrt{N}+1}\rfloor}{\lfloor \frac{N}{i}\rfloor}$$

This is done in $O(\sqrt{N})$ which is fast enough for the given constraints.