UVa 10830

From Algorithmist
Jump to navigation Jump to search

10830 - A New Function[edit]

Summary[edit]

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

Explanation[edit]

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.

Gotcha's[edit]

Watch out for overflows, especially in the binary search: can overflow if you use ints!

Notes[edit]

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[edit]

2
100
200000000
0

Output[edit]

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