Editorial for COCI '16 Contest 6 #4 Savršen


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Instead of looking for the divisors of the given numbers (which is too slow), we can take a reverse approach, similar to the sieve of Eratosthenes: for each number d = 1, 2, \dots, B check which number's divisor it is, i.e., iterate over its multiples between A and B and for each multiple V, increase its sum of divisors: sum[V] += d. In the end, we iterate over the given array summing up the required absolute differences.

At first glance, it seems that this approach could be too slow, but it is empirically seen that it is not. Theoretically, we can deduce it this way: for each divisor d, we iterate over \frac B d multiples, which gives us the total complexity of \frac B 1 + \frac B 2 + \dots + \frac B B, i.e., B \times (1 + \frac 1 2 + \dots + \frac 1 B), which is approximately B \ln B.


Comments

There are no comments at the moment.