< Back to forum

codechef problem GCDQ

Can anyone please explain how to solve the GCDQ PROBLEM(https://www.codechef.com/problems/GCDQ) ?

codechef C/C++

Asked by: arkaprava_roy on April 7, 2019, 6:34 p.m. Last updated on April 7, 2019, 6:34 p.m.

Enter your answer details below:


Enter your comment details below:




1 Answer(s)

avatar

In this question, for each query you have to find the greatest common divisor of array excluding the range [l, r].  So you have to precompute prefix gcd array as well as suffix gcd array. 

Prefix[i]  will store greatest common divisor of all  elements in the range [0,i]  i.e. Prefix[i] = gcd(Prefix[i-1],A[i]).

Similarly Suffix[i] will store greatest common divisor of all elements in the range [i, n-1]. 

Suffix[i]  = gcd(Suffix[i+1],A[i]).

Hence, if range given in the query is [l,r] then gcd of array excluding the range [l, r]  will be equal to gcd(Prefix[l-1],Suffix[r+1]).

Raghav_Grover last updated on April 7, 2019, 6:34 p.m. 0    Reply    Upvote   

Instruction to write good question
  1. 1. Write a title that summarizes the specific problem
  2. 2. Pretend you're talking to a busy colleague
  3. 3. Spelling, grammar and punctuation are important!

Bad: C# Math Confusion
Good: Why does using float instead of int give me different results when all of my inputs are integers?
Bad: [php] session doubt
Good: How can I redirect users to different pages based on session data in PHP?
Bad: android if else problems
Good: Why does str == "value" evaluate to false when str is set to "value"?

Refer to Stack Overflow guide on asking a good question.