There are many heuristics that can be applied to this problem. Some of them are mentioned below here.

Solution 1: Prime factorisation

We can try to solve the problem by considering each prime factor independently, and combining them at the end. For each prime factor ~x~, there are ~\lfloor \frac{N}{x} \rfloor~ elements which contain ~x~ as a factor. We can find the lowest index ~a~ such that ~p_a~ is a multiple of ~x~ using binary search; then, we disregard all elements with indices ~\le a~ and repeat the process to find the rest of the elements. Once we have found all elements which are multiples of ~x~, we can repeat the same process, binary searching on these elements, to find the elements which are multiples of ~x^2~, and so on. This is sufficient for ~10\%~ of the points.

Our algorithm now consists of multiple rounds; in each round, we need to find ~y~ elements which are multiples of ~x~ out of a set containing ~z~ indices. Let's try to optimise each round.

Currently, with our binary searches, we use slightly less than ~y \times \lceil \log_2 z \rceil~ queries. A simpler strategy is to query ~z-1~ of the ~z~ indices in the set individually to determine which elements are multiples of ~x~. If we combine the two strategies, we can perform a round in no more than ~\min(z-1, y \times \lceil \log_2 z \rceil)~ queries. This is sufficient for ~40\%~ of the points.

There is a more complicated strategy to perform a round. First, query the ~B~ lowest elements in the set. If at least one of these elements is a multiple of ~x~, then we perform our binary search as before to find the desired element. Otherwise, we can remove these ~B~ elements from the set, and repeat the process. This uses no more than ~\lceil \frac{z}{B} \rceil - 1 + y \times \lceil \log_2 B \rceil~ queries. The optimal value of ~B~ is different for each round, and can be found using a binary or ternary search. This is sufficient for ~70\%~ of the points. Notice that by choosing ~B = 1~, we perform the linear search from before, and by choosing ~B = z~, we perform the binary search from before. Thus, we can forget about implementing the linear or binary search separately.

Let ~res_i~ be the current product of the factors of ~p_i~ that we have found so far, at any time in our algorithm. Originally, ~res_i = 1~ for all ~1 \le i \le N~, and when our algorithm finishes, ~res_i = p_i~ for all ~1 \le i \le N~. When we perform a round checking for multiples of the power of some prime ~x~, for each element ~i~ that we find, our algorithm multiples ~res_i~ by ~x~. Consider performing all rounds checking multiples of powers of ~2~, then performing all rounds checking multiples of powers of ~3~, and so on for each prime. Then, we notice that once ~res_i * x > N~ for the current prime ~x~, ~res_i~ must equal ~p_i~, since ~res_i~ cannot be multiplied later on in our algorithm without exceeding ~N~. This means that for all future rounds, we can discard checking element ~i~. In this manner, we can reduce the size of the sets of indices that we check in each round. This is sufficient to obtain ~90\%~ of points. For full points, we need a different approach…

Solution 2: Finding elements in order, abusing randomness

Instead of trying to find the prime factorisation of each number, we can try the easier strategy of directly finding the position of each element in some order. If we are trying to find the position of element ~x~, then we would want to avoid querying any subarray that contains any multiple of ~x~ (other than ~x~). Thus, it makes intuitive sense to find the position of elements in descending order; then, when we try to find the position of element ~x~, we would already know which subarrays to avoid.

The positions of the multiples of ~x~ (other than ~x~) will be known, and they will split the entire range into several subranges. We can only glean information by querying within a single subrange. Note that our query allows us to determine if element ~x~ is present in a given subarray, as long as that subarray is part of a single subrange.

Now, we will abuse the randomness of the data. We will start by determining which subrange element ~x~ lies in. This can be done by iterating through the subranges in decreasing order of length, short-circuiting when we find the required subrange; this is optimal as longer subranges are more likely to contain element ~x~. If we get to the final subrange, then we do not need to waste an extra query since this final subrange must contain element ~x~.

Once we have found the subrange that element ~x~ lies in, a simple binary search suffices to find its exact position. Some positions within this subarray may already be known to contain other values, so these positions can be excluded from the binary search. If all optimisations are made, full points will be obtained.