Editorial for DMPG '18 S5 - Mimi and Division

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: Kirito

For 20\% of points, it suffices to iterate through all elements in the range [l,r] and check if they are divisible by x in \mathcal O(N) and update a number in \mathcal O(1).

Time Complexity: \mathcal O(QN)

For the remaining 80\% of points, we can divide the array into \mathcal O(\sqrt N) blocks of size \mathcal O(\sqrt N). Maintain an array A[1, 2, \ldots 200\,000] for each block, where A[i] is the number of elements in the corresponding block divisible by i.

An update can be done in \mathcal O(\sqrt x) time, as there are no more than 2\sqrt x factors of any positive integer x.

A query can be done in \mathcal O(\sqrt N) time: a query will iterate over no more than 2\sqrt N individual elements and \sqrt N blocks. The individual elements can be checked using the modulo operator, and the blocks can be queried using the lookup table A.

Time Complexity: \mathcal O(N \sqrt A + Q \sqrt N + Q \sqrt A), where A is the maximum value of any element in the array.


  • -10
    DarthVader336  commented on May 23, 2018, 11:59 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.

    • 22
      Plasmatic  commented on Feb. 3, 2019, 12:17 a.m.

      \sqrt{no} \sqrt{u}