Range GCD (RGCD) Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Tushar Kadam
Tester: Chirag Shetty
Editorialist: Devansh Solanki

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Square Root Decomposition or Segment Tree with lazy propagation

PROBLEM:

You are given an array of numbers. You can perform two kinds of operations on it. In one of the operations, you have to multiply the number in the given range with a given number and in another operation, you have to find the gcd of all the numbers in the given range and print the output of this gcd calculation.

QUICK EXPLANATION:

The brute force approach to this problem is that one can just update execute the given queries and calculate the solution but that is clearly not the right approach as it will exceed out the time limit. So by this, we know that traversing the entire range from L to R is not the right approach and hence we need to find a way to go around that. This can be approach is through square root decomposition.

EXPLANATION:

We can solve this problem using square root decomposition. We divide the array into blocks of size sqrt(n) and store the gcd of each block in an array. After this we handle both the queries in the following manner:

  • In case of the update query, for the blocks which entirely in the given range, we do not actually update the elements of the array but just update the gcd by just multiplying the gcd with the given number. For blocks which are the edges of the range i.e partially included in the range we first have to calculate the gcd of the block then divide it by the current gcd of that block in the gcd array and multiply the result(let it be called multiplication factor) with the result of the division and then finally update the elements which are included in the range by the given number in the query and after this update the gcd of the block in the gcd array. This might seem complicated but it’s done in order to ensure that we don’t have to traverse the entire range.

    • Multiplication factor is calculated because we do not update the elements every time an update query in made instead we only update them when it is required.

  • When we have to calculate the gcd of the range we can just take the gcd of the blocks in the range form the gcd array. But not so soon, this is true for blocks which are entirely included in the range. For the corner blocks at the ends of the range that are partially included we need to again do some computation in order to make sure we are extracting the correct gcd.this is similar as above in which we have to check if the numbers have been updated early on or not. So we calculate the gcd of the block divide it by gcd of the block in the gcd array which will give us the multiplication factor.we will multiply this number with each element in the block then calculate the gcd of the elements of that block which are included in the range and include this gcd while calculating the gcd of the full blocks. hence now we simply just have to calculate the gcd of the gcd of corner blocks and full blocks this will give us the answer

ALTERNATIVE SOLUTION:

Seg Tree + Lazy Propagation

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

6 Likes