# UVa 10830

## Summary

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

## Explanation

A number ${\displaystyle d}$ appears ${\displaystyle \lfloor N/d\rfloor }$ times as a divisor of the numbers ${\displaystyle 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: ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle l}$, we can binary search on the last value ${\displaystyle h}$, for which ${\displaystyle \lfloor N/l\rfloor =\lfloor N/h\rfloor }$. So

${\displaystyle \sum _{l\leq d\leq h}d(\lfloor N/d\rfloor -1)}$

${\displaystyle =\sum _{l\leq d\leq h}d(\lfloor N/l\rfloor -1)}$

${\displaystyle =(\lfloor N/l\rfloor -1)\sum _{l\leq d\leq h}d}$

${\displaystyle =(\lfloor N/l\rfloor -1){\frac {1}{2}}(h-l+1)(l+h)}$. If we binary search in ${\displaystyle [l\ldots N]}$ it is still gets TLE. But if we tweak the upper bound, using the observation that ${\displaystyle 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: ${\displaystyle m={\frac {l+h}{2}}}$ can overflow if you use ints!

## Notes

There is probably a more elegant algorithm, anybody sees it? kcm1700's comment : There's no need to use binary search. We can calculate the length of each interval.

## Input

2
100
200000000
0


## Output

Case 1: 0
Case 2: 3150
Case 3: 12898681201837053