My solution: Cutting the array into blocks, so I can now update a segment with O(sqrt n) each query; therefore, I can get the increase in O(1) while scanning each factor (at most 180 in total). It is obvious that I should prepare all the factors for each number.
The complexity of the algorithm is O((sqrt(n) + 180) * m + 180 * n).
and .. I reduce a lot of modular and divide operations to get this AC. :P
