This problem is from Codechef January challenge. Click on the link to try this problem on your own.

The problem statement is as follows.

Given an array of size N and two indices L and R. We need to find the GCD (Greatest Common Divisor) of all the array elements except in the range [L,R]. The indices start from 1. We have to answer multiple queries of this type.

An obvious solution could be to find the GCD of all the elements from [1,L-1] and [R+1,N] and find the GCD between these two numbers. But this solution is O(n) for each query in the worst case.

First let us pre-process these array to gain some efficiency. Define cumulative GCD as follows.

If A is an array of N elements, the cumulative GCD of an array A from left to right consists of the following.

cgcd[0] = A[0]

cgcd[1] = gcd(cgcd[0], A[1])

cgcd[2] = gcd(cgcd[1], A[2])

…. and so on

Lets create an array fgcd which stores the cumulative GCD from

*left to right*. Also create an array bgcd which stores the cumulative GCD from*right to left*.After calculating these values, answering the query is simply finding the GCD of fgcd(L-1) and bgcd(R+1).

Here is the C++ implementation of the above. This each query takes only O(1) time and it takes O(n) extra space to store the pre-processed values.