# GCD Queries - Greatest Common Divisor 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.

**Problem Description:** The problem basically wants you to utilize all elements from index 1 to L-1 and then from index R+1 to N and find their gcd also need to exclude all elements of range[L, R] if we are considering 1 based indexing for solving the given problem and if 0 based indexing then need to utilize elements from [0, L-2] and [R, n-1] that excludes elements from the range[L-1, R-1].

**Input:** The first line of input contains an integer T denoting number of test cases. For each test case, the first line will contain two space-separated integers N, Q. The next line contains N space-separated integers denoting array A. For next Q lines, each line will contain a query denoted by two space-separated integers L, R.

**Output:** For each query, print a single integer representing the answer to that query.

**Examples:**

Input:
T = 1
N = 3, Q = 3
[2,6,9]
L R
1,1
2,2
2,2
Output:
3
1
2
Explanation:
For the first query, the remaining part of the array will be (6, 9).
So the answer is 3.
For the second query, the remaining part of the array will be (2, 9).
So answer is 1.
For the third query, the remaining part of the array will be (2).
So the answer is 2.

(1) Brute Force Approach:In this approach, we will calculate the gcd of the array from index 1 to

L-1and from indexR+1ton. Since we need to skip the range[L, R]for each query.To calculate gcd we will use the

Euclid algorithmas it is very fast as compared to the brute force gcd method.The time complexity for the Euclid algorithm is

log(n).Pseudo Code:The time complexity for the brute force approach in the worst case is

O(N)for each query therefore forQqueries overall time complexity reaches to(N*Q).Program to illustrate the working of Brute force approachOutput:(2) Prefix and Suffix Array Approach:In this approach, we will optimize the time complexity with the help of prefix and suffix array.

pref[L-1]andsuf[R+1]since they are storing the prefix and suffix gcd in them.Time complexity for the above case reduces from O(N*Q) to

O(N)since for each query it takes O(1) time find gcd from [0,L) and from [R+1,n).Space Complexity: O(n)Program to illustrate the working of prefix and suffix array approach

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: