Request pre-processing

Question

I have an array of integers and I need to answer y queries. Each query has 3 integers (Number, Left index, Right Index). I need to compute GCD (Number, array [i]). I am in the range from left to right as indicated in the request. Now I need to print the maximum number that I can get in the GCD calculation.

Example → Assume that the numbers are 4 5 8 Query-> (6,1,3) --- (number, left pointer, right index) GCD (6,4) = 2 GCD (6,5) = 1 GCD ( 6.8) = 2

So, answer 2. What if I have 10 ^ 5 elements in the array and I need to answer 10 ^ 5 queries?

I am going to do some preprocessing but don't understand.

Answer 1

You can store the index for each step that is in the factorization of the elements of the array, and for the request number, the indexes of its factorization in the given range and find the maximum GCD between them.

Indexes can be implemented as lists with pairs (position in the array, main power), while the segment search is in the log.

eg. if the array is [4, 5, 8, 12, 3], we have 3 different primes (2, 3, 5) and indices:

2 -> [(0, 4), (2, 8), (3, 4)]
3 -> [(3, 3), (4, 3)]
5 -> [(1,5)]

For the query (6, 1, 3), since 6 = 2 * 3 should look like in subindexes:

2 -> [(2, 8), (3, 4)]
3 -> [(3, 3)]

Going “parallel” through these subindexes and creating a GCD product for prime numbers (minimum primary power in the number of queries and the second element of the index) will lead to the creation of all possible GCDs.