Problem solving with programming: GCD queries

Problem solving with programming: GCD queries
Codechef January challenge

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).

 int t;


 cin >> t;


 while( t-- )


 {


  int n,q;


  cin >> n >> q;


  vector<int> nums(n);


 


  int i,j;


  for( i = 0; i < n; i++ )


  {


   cin >> nums[i];


  }


  


  vector<int> fgcd(n);


  vector<int> bgcd(n);


  fgcd[0] = nums[0];


  for( i = 1; i < n; i++ )


  {


   fgcd[i] = gcd(fgcd[i-1],nums[i]);


  }


  bgcd[n-1] = nums[n-1];


  for( i = n-2; i >= 0; i-- )


  {


   bgcd[i] = gcd(bgcd[i+1],nums[i]);


  }


 


  for( i = 0; i < q; i++ )


  {


   int l,r;


   cin >> l >> r;


   l--; r--;


   if( l == 0 )


   {


    cout << bgcd[r+1] << endl;


   }


   else if( r == n-1 )


   {


    cout << fgcd[l-1] << endl;


   }


   else


   {


    cout << gcd(fgcd[l-1], bgcd[r+1]) << endl;


   }


  }


 }

int gcd(int x, int y)


{


 int r = y % x;


 while( r > 0 )


 {


  y = x;


  x = r;


  r = y % x;


 }


 return x;


}

Read full article from Problem solving with programming: GCD queries