Short Tutorial:

There are at most 66 distinct prime factors of a number nn where n105n \leq 10^5. Let the prime factorization of xx be p1e1×p2e2×p3e3××pkekp_1^{e_1}\times p_2^{e_2} \times p_3^{e_3}\times … \times p_k^{e_k}. The LCM of some selected numbers will be divisible by xx if each pieip_i^{e_i} exists as a factor of at least one selected number. We can represent every factor by a mask. Let dp[mask]dp[mask] be the minimum index ii such that the it is possible to select some integers from the segment al,al+1,,aia_l, a_{l+1}, …, a_{i} and their LCM is divisible by each of the factors of maskmask and no two consecutive integers are selected. Let a mask be 0110101101.

If the last set bit of the mask is the second bit from the left, then the previous state from where we got 0110101101 is 0010100101.

If the last set bit of the mask is the third bit from the left, then the previous state from where we got 0110101101 is 0100101001.

If the last set bit of the mask is the fifth bit from the left, then the previous state from where we got 0110101101 is 0110001100.

So, dp[01101]=min(f(dp[00101],2),f(dp[01001],3),f(dp[01100],5))dp[01101] = \min(f(dp[00101], 2), f(dp[01001], 3), f(dp[01100], 5)) where f(i,k)f(i, k) is the minimum index jj such that j==ij==i or i+1<ji+1< j and aja_j is divisible by the factor corresponding to the kk-th factor of the mask from left. Here, ji+1j\neq i+1 because we cannot pick ai+1a_{i+1} after selecting aia_i. So, if aia_i is divisible by the kk-th factor, f(i,k)f(i,k) is ii. Otherwise, f(i,k)f(i,k) is the minimum index jj such that aja_j is divisible by the kk-th factor and ji+1j\neq i+1. aja_j can be found by upper bound of i+1i+1 in the list of indices of multiples of the current factor which should be precalculated. Thus, we can compute dp[01101]dp[01101].

Similarly, we can compute dp[mask]dp[mask] for all possible masks. If dp[11111]rdp[11111] \leq r, then the answer is Yes. Otherwise No.

The time complexity is O(q×k×2k×logn)O(q\times k\times 2^k \times \log{n}) where kk is the maximum number of distinct prime factors of xx.

Detailed Tutorial:

There are at most 66 distinct prime factors of a number nn where n105n \leq 10^5. Let the prime factorization of xx be p1e1×p2e2×p3e3××pkekp_1^{e_1}\times p_2^{e_2} \times p_3^{e_3}\times … \times p_k^{e_k}​. The LCM of some selected numbers will be divisible by xx if each pieip_i^{e_i}​ exists as a factor of at least one selected number.

Let, x=p1e1×p2e2×p3e3x = p_1^{e_1}\times p_2^{e_2} \times p_3^{e_3} and a=p1e1a=p_1^{e_1}, b=p2e2b=p_2^{e_2} , c=p3e3c=p_3^{e_3}. We have to select all the factors {a,b,c}\{a, b, c\} in some order. For example, consider the subarray A[lr]A[l…r]. Let it be [a, b, a, a, c, a, c, b, a, a][a\prime, ~ b\prime, ~ a\prime, ~ a\prime, ~ c\prime, ~ a\prime,~ c\prime, ~ b\prime,~ a\prime,~ a\prime]. Where yy\prime is a multiple of yy. To get the optimal result, first, we have to select the first multiple of the factor bb (which is bb \prime) from the left at index 22 (consider l=1l=1). Then we must select the multiple of the factor aa at index 44 and finally the multiple of the factor cc at index 77. So the optimal order of selecting factors in this case is bacb \rightarrow a \rightarrow c. Let the last selected index be zz. In this order of selection, z=7z=7.

If we try another permutation acba \rightarrow c \rightarrow b, the selected indices will be 1, 5, 81, ~5, ~8 where z=8z=8. 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 zz where the segment A[lz]A[l … z] contains all the factors. Among the values of zz for all permutations, if the minimum one is less than or equal to rr, then the answer of that query is Yes. Otherwise, No.

Since there are most 66 distinct prime factors, there are at most 262^6 subsets of factors. For each subset, we will calculate the minimum index zz such that it is possible to select some integers from the segment A[lz]A[l…z] and their LCM is divisible by all the elements of that subset. Consider the above subarray. For the subset {a,c}\{a, c\}, the minimum index required to select both aa and cc is 55 if we select aa from the first index and cc 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 {a,b,c}\{a, b, c\}. Now the question is, how can we calculate the minimum index zz for a subset of factors? Suppose, we want to calculate the minimum index for the subset {a,b,c}\{a, b, c\}. 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 {a,b,c}\{a, b, c\}. If the last selected factor is aa, then the previous subset must be {b,c}\{b, c\}. If the last selected factor is bb, then the previous subset must be {a,c}\{a, c\}. For cc, the previous subset must be {a,b}\{a, b\}. 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 aa as the last selected factor, the previous subset is {b,c}\{b, c\}. The minimum index required to select the subset {b,c}\{b, c\} is 55. So, we must select the multiple of aa from such an index that is greater than or equal to 55 but not 66 (we can’t select any factor from index 66 as we have already selected one from index 55). The lowest index of a multiple of aa after index 66 is 99. So if we consider aa as the last selected factor, we get 99 as the value of zz for the subset {a,b,c}\{a, b, c\}.

Now, if we consider bb as the last selected factor, the previous subset is {a,c}\{a, c\}. The minimum index required to select the subset {a,c}\{a, c\} is 55. So, we must select the multiple of bb from such an index that is greater than or equal to 55 but not 66. The lowest index of the multiple of bb after index 66 is 88. So if we consider bb as the last selected factor, we get 88 as the value of z for the subset {a,b,c}\{a, b, c\}.

Similarly, if we consider cc as the last selected factor, the previous subset is {a,b}\{a, b\}. The minimum index required to select the subset {a,b}\{a, b\} is 44. So, we must select the multiple of cc from such an index that is greater than or equal to 44 but not 55. The lowest index of multiple of cc after index 44 is 77. So if we consider cc as the last selected factor, we get 77 as the value of z for the subset {a,b,c}\{a, b, c\} which is the best result in this case.

Formally, let dp[mask]dp[mask] be the value of zz for the corresponding subset of the mask. So, dp[111]=min(f(dp[011],a),f(dp[101],b),f(dp[110],c))dp[111] = \min(f(dp[011], a), f(dp[101], b), f(dp[110], c)). where f(i,d)f(i, d) is the minimum index jj such that j==ij==i or i+1<ji+1< j and AjA_j​ is divisible by dd. Here, ji+1j\neq i+1 because, we cannot pick Ai+1A_{i+1}​ after selecting AiA_i. So, if AiA_i is divisible by ddf(i,d)f(i,d) is ii. Otherwise, f(i,d)f(i,d) is the minimum index jj such that AjA_j is divisible by dd and ji+1j\neq i+1.

Consider the following diagram of state transition.

There are 66 possible permutations of {a,b,c}\{a, b, c\}. Notice, here we are checking all possible permutations of the subset technically in O(k×2k)O(k\times 2^k) complexity instead of O(k!)O(k!). 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 O(k×2k)O(k\times 2^k) 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 O(k×2k×logn)O(k\times 2^k \times \log{n}) per query. This complexity can be reduced by precalculating the next index of the multiple of factors up to 105\sqrt{10^5} for each index and finding them in O(1)O(1) instead of logn\log{n}. But this optimization is not required to be accepted in this problem.

Author’s Solution: https://ideone.com/KGlyls

Statistics

83% Solution Ratio
adnan_tokyEarliest, Mar '22
adnan_tokyFastest, 0.4s
Mestu_PaulLightest, 6.4 MB
adnan_tokyShortest, 2292B
Toph uses cookies. By continuing you agree to our Cookie Policy.