# UVa 10830

## Summary

Given a number $N$ , find the cumulative sum of all the divisors of all numbers $\leq N$ , excluding 1 and the number itself.

## Explanation

A number $d$ appears $\lfloor N/d\rfloor$ times as a divisor of the numbers $1\ldots N$ . (Try it on paper if you don't see this) Because the number itself should not be counted, we have to substract 1 from this. This leads to this algorithm: $\sum _{2\leq d\leq N}d(\lfloor {\frac {N}{d}}\rfloor -1)$ . This formula gives the right results, but is way to slow.

When studying the sequence of values for $\lfloor N/d\rfloor$ , we see that it is decreasing and that (especially at the end) the values are the same for quite a long time. Given $l$ , we can binary search on the last value $h$ , for which $\lfloor N/l\rfloor =\lfloor N/h\rfloor$ . So

$\sum _{l\leq d\leq h}d(\lfloor N/d\rfloor -1)$ $=\sum _{l\leq d\leq h}d(\lfloor N/l\rfloor -1)$ $=(\lfloor N/l\rfloor -1)\sum _{l\leq d\leq h}d$ $=(\lfloor N/l\rfloor -1){\frac {1}{2}}(h-l+1)(l+h)$ . If we binary search in $[l\ldots N]$ it is still gets TLE. But if we tweak the upper bound, using the observation that $h-l$ usually doesn't change much for two adjacent intervals, we can get AC.

## Gotcha's

Watch out for overflows, especially in the binary search: $m={\frac {l+h}{2}}$ can overflow if you use ints!