## Editorial for DMPG '18 S5 - Mimi and Division

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**Author:

For of points, it suffices to iterate through all elements in the range and check if they are divisible by in and update a number in .

**Time Complexity:**

For the remaining of points, we can divide the array into blocks of size . Maintain an array for each block, where is the number of elements in the corresponding block divisible by .

An update can be done in time, as there are no more than factors of any positive integer .

A query can be done in time: a query will iterate over no more than individual elements and blocks. The individual elements can be checked using the modulo operator, and the blocks can be queried using the lookup table .

**Time Complexity:** , where is the maximum value of any element in the array.

## Comments

This comment is hidden due to too much negative feedback. Click here to view it.