Editorial for An Animal Contest 4 P2 - Lavish Lights
Submitting an official solution before solving the problem yourself is a bannable offence.
We can solve this problem for each query by finding the first prefix LCM such that does not divide . If such a does not exist, that means that all lights are on at time ( is a multiple of all integers in array ), and we can output
To answer these queries efficiently, we can construct a prefix LCM array, stopping when the prefix LCM exceeds the maximum allowed value, . For each query, we can run binary search and check if divides all numbers up to some index .
Be careful of the case when ; is a multiple of all integers.
If binary search isn't for you, observe that there are only a maximum of around positions where the light at position will be the first to be off. We can find these positions by considering the prefix LCM and then for each query we can run linear search over these positions.
Again, be careful about edge cases such as when .
It is even possible to perform binary search instead of linear search in solution 2 to achieve a complexity of .