## PROBLEM LINK:

**Author:** Misha Chorniy

**Tester:** Lewin Gan

**Editorialist:** Adarsh Kumar

## DIFFICULTY:

Medium

## PREREQUISITES:

Familiarity with GCD, Dynamic Programming

## PROBLEM:

You are given a sequence A with N elements and Q queries on this sequence. In each query, you are given two indices L and R; you should compute the maximum value of the greatest common divisor (GCD) of two elements A_x, A_y satisfying L \le x < y \le R.

## EXPLANATION:

We will try to pre-compute the answers for all the possible query ranges. For the same purpose create two two-dimensional array TEMP[N][N] and ANS[N][N], where N=10005. We will define ANS[L][R] = max(TEMP[x][y]) â L \le x < y \le R.

**Observation**: Letâs take a look at multiple of any particular numbers D. Say the multiples of D in the array are located at i_1,i_2,i_3,..i_k. Now, any query range which contains atleast two of the above index will have answer \ge D (Why?). If we update TEMP[i_j][i_{j+1}] = max(TEMP[i_j][i_{j+1}],D) â j < k, and re-compute ANS array, we can see it will cover all the required query ranges that needs to be updated.

We will try to build our solution using the above observation. Iterate over each of the numbers in the array, find their respective divisors in O(\sqrt{A[i]}). Corresponding to every divisor, find the right most index j < i where multiple of this divisor has appeared. You can use another array to ease this process. After finding such j you just need to update TEMP[j][i]=max(TEMP[j][i],\text{corresponding divisor}).

Once you have iterated over all the numbers, compute ANS[x][y] â 1 \le x < y \le N. You can have a look at pseudo-code for the same,

```
for i=1...N-1:
ANS[i][i+1]=TEMP[i][i+1]
for l=3...N:
for i=1...(N-l+1):
j = i+l-1
ANS[i][j] = max(ANS[i+1][j],ANS[i][j-1])
ANS[i][j] = max(ANS[i][j],TEMP[i][j])
```

You can answer every query in O(1) now.

## Time Complexity:

O(N^2+Q).