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

Edited by author 25.10.2015 00:21