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.
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 check which number's divisor it is, i.e., iterate over its multiples between and and for each multiple , 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 , we iterate over multiples, which gives us the total complexity of , i.e., , which is approximately .
Comments