Query Preprocessing

Question

I have array of x integers and i need to answer y queries. Each query have 3 integers ( Number, Left index, Right Index). I need to calculate GCD(Number, array[i]). i is in the range left-right as as specified in the query. Now i need to output the maximum number that i can obtain in the GCD calculation.

Example--> Suppose numbers are 4 5 8 Query-> (6,1,3)---(Number,Left Index,Right index) GCD(6,4) = 2 GCD(6,5) = 1 GCD(6,8) = 2

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

I am thinking to do some preprocessing but not getting any idea.

Answer 1

It is possible to store index for each prime that is in factorization of array elements, and for query number look at indices of it's factorization in range that is given and find maximal GCD between them.

Indices can be implemented as lists with pairs (position in array, prime power), with that searching for segment is in log.

E.g. if array is [4, 5, 8, 12, 3] than 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 query (6, 1, 3), since 6=2*3 has to look in sub-indices:

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

Going 'parallel' through these sub-indices, and making product of GCD's for primes (minimum of prime power in query number and index second element) will produce all possible GCD's.