There are at most distinct prime factors of a number where . Let the prime factorization of be . The LCM of some selected numbers will be divisible by if each exists as a factor of at least one selected number. We can represent every factor by a mask. Let be the minimum index such that the it is possible to select some integers from the segment and their LCM is divisible by each of the factors of and no two consecutive integers are selected. Let a mask be .
If the last set bit of the mask is the second bit from the left, then the previous state from where we got is .
If the last set bit of the mask is the third bit from the left, then the previous state from where we got is .
If the last set bit of the mask is the fifth bit from the left, then the previous state from where we got is .
So, where is the minimum index such that or and is divisible by the factor corresponding to the -th factor of the mask from left. Here, because we cannot pick after selecting . So, if is divisible by the -th factor, is . Otherwise, is the minimum index such that is divisible by the -th factor and . can be found by upper bound of in the list of indices of multiples of the current factor which should be precalculated. Thus, we can compute .
Similarly, we can compute for all possible masks. If , then the answer is Yes. Otherwise No.
The time complexity is where is the maximum number of distinct prime factors of .
There are at most distinct prime factors of a number where . Let the prime factorization of be . The LCM of some selected numbers will be divisible by if each exists as a factor of at least one selected number.
Let, and , , . We have to select all the factors in some order. For example, consider the subarray . Let it be . Where is a multiple of . To get the optimal result, first, we have to select the first multiple of the factor (which is ) from the left at index (consider ). Then we must select the multiple of the factor at index and finally the multiple of the factor at index . So the optimal order of selecting factors in this case is . Let the last selected index be . In this order of selection, .
If we try another permutation , the selected indices will be where . This order of selection is not optimal.
As we don’t know the order of factors to get the optimal result, we can try all possible permutations of the factors. Then for each permutation, we can take the minimum index where the segment contains all the factors. Among the values of for all permutations, if the minimum one is less than or equal to , then the answer of that query is Yes. Otherwise, No.
Since there are most distinct prime factors, there are at most subsets of factors. For each subset, we will calculate the minimum index such that it is possible to select some integers from the segment and their LCM is divisible by all the elements of that subset. Consider the above subarray. For the subset , the minimum index required to select both and is if we select from the first index and from the fifth index. The table below shows the list of the minimum indexes for all possible subsets of factors of the subarray.
The solution to the problem comes from the minimum index for the subset . Now the question is, how can we calculate the minimum index for a subset of factors? Suppose, we want to calculate the minimum index for the subset . There are three factors in this subset. As we mentioned above, the factors are selected in some order, certainly, there were exactly two factors before selecting the third one. Now we don’t know which factor is selected at the last time in the optimal permutation. This factor can be one of these three factors . If the last selected factor is , then the previous subset must be . If the last selected factor is , then the previous subset must be . For , the previous subset must be . So, we consider each factor of the subset as the last selected factor and find the best result among all the possible ways.
Again consider the above subarray. If we consider as the last selected factor, the previous subset is . The minimum index required to select the subset is . So, we must select the multiple of from such an index that is greater than or equal to but not (we can’t select any factor from index as we have already selected one from index ). The lowest index of a multiple of after index is . So if we consider as the last selected factor, we get as the value of for the subset .
Now, if we consider as the last selected factor, the previous subset is . The minimum index required to select the subset is . So, we must select the multiple of from such an index that is greater than or equal to but not . The lowest index of the multiple of after index is . So if we consider as the last selected factor, we get as the value of z for the subset .
Similarly, if we consider as the last selected factor, the previous subset is . The minimum index required to select the subset is . So, we must select the multiple of from such an index that is greater than or equal to but not . The lowest index of multiple of after index is . So if we consider as the last selected factor, we get as the value of z for the subset which is the best result in this case.
Formally, let be the value of for the corresponding subset of the mask. So, . where is the minimum index such that or and is divisible by . Here, because, we cannot pick after selecting . So, if is divisible by , is . Otherwise, is the minimum index such that is divisible by and .
Consider the following diagram of state transition.
There are possible permutations of . Notice, here we are checking all possible permutations of the subset technically in complexity instead of . To implement the whole process, we just need to represent every subset as a mask. Then our only DP state is the mask. Thus we can solve the task in for each query if we do some preprocessing to find the lowest index of each factor after any index efficiently. It can be done by using the upper bound in the list of indices of multiples of the current factor which should be precalculated. It gives a complexity per query. This complexity can be reduced by precalculating the next index of the multiple of factors up to for each index and finding them in instead of . But this optimization is not required to be accepted in this problem.
Author’s Solution: https://ideone.com/KGlyls