I would like to know how to solve this problem faster, as I pass it with 2.8s.

Posted by

lyonlys 25 Oct 2015 00:20

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*