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, \dots, 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.