Editorial for DMOPC '14 Contest 3 P4 - Not Enough Testers!
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.
Author:
Let be the maximum of
over all the cases. We can precompute the number of factors for each number from
to
using a method like the Sieve of Eratosthenes. We iterate from
to
, and for each number we increase the number of factors of all its multiples by 1. The total time complexity is
times the partial sum for the harmonic series up to
, which can be proven to be
in total. Then, for each possible value of
, we can put the number of numbers that have
as a factor into a list and then we can use binary search on the list associated with a query to answer all the queries. Since a number
has at most
factors, we can also use a prefix sum array here.
Time Complexity: or
Comments