## Editorial for An Animal Contest 4 P2 - Lavish Lights

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: ThingExplainer

Solution 1:

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 -1.

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.

Time Complexity:

Solution 2:

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 .

Time Complexity:

It is even possible to perform binary search instead of linear search in solution 2 to achieve a complexity of .