## 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.**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