10830 - A New Function
Given a number , find the cumulative sum of all the divisors of all numbers , excluding 1 and the number itself.
A number appears times as a divisor of the numbers . (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: . This formula gives the right results, but is way to slow.
When studying the sequence of values for , we see that it is decreasing and that (especially at the end) the values are the same for quite a long time. Given , we can binary search on the last value , for which . So
. If we binary search in it is still gets TLE. But if we tweak the upper bound, using the observation that usually doesn't change much for two adjacent intervals, we can get AC.
Watch out for overflows, especially in the binary search: can overflow if you use ints!
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.
2 100 200000000 0
Case 1: 0 Case 2: 3150 Case 3: 12898681201837053