## Introduction

This blog will discuss the solution to the problem of finding the maximum divisor of two integers in a range.

### Problem Statement

We are given two numbers, **a** and **b**. After that, we will be given q queries containing two integers, **l** and **r**. Let us define a set **S** with common divisors of **a** and **b**, which lie in the **l** and **r**. We need to find the maximum element in this set **S**, and if there is no element in this set, we need to print -1. So before we deep dive into the answer, we should look at an example to understand the problem better.

### Sample Example

**Input:**

8 12

4

2 4

3 6

2 3

12 13

**Output:**

For 8 and 12, the gcd is four, and its divisors are [1, 2, 4], so the common divisors are [1, 2, 4]

In the range [2, 4], the max common divisor is 4.

In the range [3, 6], the max common divisor is 4.

In the range [2, 3], the max common divisor is 2.

In the range [12, 13], there is no common divisor between 12 and 13 so we print -1.

## Approach

- To solve this problem, of finding maximum divisors in a range. We will first find out the gcd of given numbers a,b.
- We will find the divisors of gcd(a,b) and we will store them in an array.
- Next, we will sort the array so that we can apply binary search on the array.
- So will find maximum common divisor in the range [l, r] by searching for a lower bound of r and upper bound for l.

The upper bound of any number x finds the position of the immediate greater element present in the array but the array should be in increasing order.

The lower bound of any number x finds the position of the immediate smaller element present in the array but the array should be in increasing order.

- If both lower and upper bound are the same, there is no common divisor in the range [l, r].
- If both lower and upper bound are not the same, we will check for the previous element of the upper bound of r since the upper bound will be greater than r, but its previous element will not be greater than r.

Must Read __Lower Bound in C++__

### Implementation in C++

```
// C++ code for Maximum Divisors in a Range
#include <bits/stdc++.h>
using namespace std;
// to find the lower bound of a number in an array
int lowerBound(int a[], int start, int end, int key)
{
if (start > end)
return end;
int mid = (start + end) / 2;
if (a[mid] == key)
return mid;
else if (a[mid] > key)
return lowerBound(a, start, mid - 1, key);
else
return lowerBound(a, mid + 1, end, key);
}
// to find the upper bound of a number in an array
int upperBound(int a[], int start, int end, int key)
{
if (start > end)
return start;
int mid = (start + end) / 2;
if (a[mid] == key)
return upperBound(a, mid + 1, end, key);
else if (a[mid] > key)
return upperBound(a, start, mid - 1, key);
else
return upperBound(a, mid + 1, end, key);
}
// driver code for Maximum Divisors in a Range
int main()
{
int a, b;
cin >> a >> b;
// inbuilt function to find gcd of two numbers
int g = __gcd(a,b);
// to store the divisors of gcd
int divisors[1000000] = {0}, count = 0;
for (int i = 1; i <= g; i++)
if (g % i == 0)
divisors[count++] = i;
int n;
cin >> n;
while (n--)
{
int low, high;
cin >> low >> high;
// to store the lower bound index of a number in an array
int id1 = lowerBound(divisors, 0, count - 1, low);
// to store the upper bound index of a number in an array
int id2 = upperBound(divisors, 0, count - 1, high);
if (low > divisors[id1] || count == 0)
id1++;
// to store the difference of both the indexes
int diff = id2 - id1;
// if zero then print -1
if (diff == 0)
cout << "-1\n";
// else print the divisor
else
cout << divisors[id2 - 1] << endl;
}
}
```

**Output:**

```
Input:
6 8
2
2 4
3 5
Output:
2
-1
```

#### Complexity Analysis

**Time Complexity: **O(max(A,B)+(N(log_{2}P + log_{2}P))

**Space Complexity: **O(min(A, B))

Check out this problem - __Next Smaller Element__