Editorial for DMPG '18 S5 - Mimi and Division
Submitting an official solution before solving the problem yourself is a bannable offence.
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.