### PROBLEM LINK:

**Author:** Praveen Dhinwa

**Tester:** Shiplu Hawlader

**Editorialist:** Lalit Kundu

### DIFFICULTY:

EASY

### PRE-REQUISITES:

GCD, Precomputation

### PROBLEM:

You are given an array **A** of integers of size **N**. You will be given **Q** queries where each query is represented by two integers **L**, **R**. You have to find the **gcd**(Greatest Common Divisor) of the array after excluding the part from range **L** to **R** inclusive (1 Based indexing). You are guaranteed that after excluding the part of the array remaining array is non empty.

1 ≤ **N**, **Q** ≤ 100000

### EXPLANATION:

If you do it naively(ie. calculating GCD of remaining array for each query), the worstcase complexity will be **O(N * Q)**.

Let’s denote by **G(L, R)**, the GCD of **A _{L}, A_{L+1} … A_{R}**. We can observe that for query

**[L, R]**, we need GCD of

**G(1, L-1)**and

**G(R+1, N)**.

So, we precalculate prefix and suffix gcd arrays.

If we have:

**Prefix**= GCD of

_{i}**A**

_{1}, A_{2}… A_{i}**Suffix**= GCD of

_{i}**A**

_{N}, A_{N-1}… A_{i}answer to query

**[L, R]**, would be GCD of

**Prefix**and

_{L-1}**Suffix**.

_{R+1}We can calculate prefix and suffix arrays in **O(N)** if we notice that:

**Prefix _{i}** = GCD(

**Prefix**,

_{i-1}**A**)

_{i}**Suffix**= GCD(

_{i}**Suffix**,

_{i+1}**A**)

_{i}Pseudo Code for building prefix and suffix arrays:

```
n,a=input
pre[n],suf[n]
//base case
pre[1]=a[1]
suf[n]=a[n]
for i=2 to n:
pre[i] = gcd(pre[i-1], a[i])
for i=n-1 to 1:
suf[i] = gcd(suf[i+1], a[i])
```

So, overall complexity would be **O((N + Q) * K)**, where **K** is a constant factor for gcd calculation.

### ALTERNATIVE SOLUTION:

Use segment trees for range gcd queries. But note that a factor of **log N** will be increased in complexity.