(1) Brute Force Approach:

In this approach, we will calculate the gcd of the array from index 1 to L-1 and from index R+1 to n. Since we need to skip the range [L, R] for each query.

To calculate gcd we will use the Euclid algorithm as it is very fast as compared to the brute force gcd method.

The time complexity for the Euclid algorithm is log(n).

Pseudo Code:

//Euclid gcd function.
int gcd(int a,int b)
{	
    //if b==0 then return a.
    if(b==0)
        return a
    else
        return gcd(b,a%b)
}

The time complexity for the brute force approach in the worst case is O(N) for each query therefore for Q queries overall time complexity reaches to (N*Q).

Program to illustrate the working of Brute force approach

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
//declare array for entire problem.
ll arr[100005];

//declare euclid gcd function.
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

int main()
{
    ll t;

    cout << "Enter number of test cases: ";
    //take input.
    cin >> t;

    while (t--) {
        //take input size of array and queries.
        ll n, q;
        cout << "Enter size of array and queries count: ";
        cin >> n >> q;

        //call solve function.
        cout << "Enter elements: ";
        for (ll i = 1; i <= n; i++)
            cin >> arr[i];

        //process queries.
        cout << "Enter queries: ";
        while (q--) {
            ll l, r;
            //take input L and R.
            cin >> l >> r;
            //initialise temporary ans=0 as 0 doesn't effect our answer.
            ll ans = 0;
            //traverse through the array from 1 to L-1
            for (ll i = 1; i < l; i++)
                ans = gcd(ans, arr[i]);
            //traverse through the array from n to R+1.
            for (ll i = n; i > r; i--)
                ans = gcd(ans, arr[i]);
            //use pref[L-1] to get gcd of numbers berfore L and use
            //suf[R+1] to get gcd of number from n to R+1.
            cout << "Final Gcd: ";
            cout << ans << "\n";
        }
    }

    return 0;
}

Output:

Enter number of test cases: 3
Enter size of array and queries count: 4 1
Enter elements: 1 2 3 4
Enter queries: 2 3
Final Gcd: 1
Enter size of array and queries count: 5 1
Enter elements: 2 4 6 8 10
Enter queries: 3 4
Final Gcd: 2
Enter size of array and queries count: 3 1
Enter elements: 10 20 30
Enter queries: 2 2
Final Gcd: 10

(2) Prefix and Suffix Array Approach:

In this approach, we will optimize the time complexity with the help of prefix and suffix array.

1. We will create two array prefix and suffix which will store the gcd of elements from index (i,i+1,i+2,....N) and from index(N,N-1,N-2,.....1) respectively.
2. For each query [L, R], we will take the gcd of pref[L-1] and suf[R+1] since they are storing the prefix and suffix gcd in them.
3. Since we need to avoid [L, R] range elements in our final gcd so for final result we take prefix[L-1] gcd with suffix[R+1] since prefix is storing gcd with index [0,n) and suffix is storing gcd with index(n,0].

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

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll arr[100005]; //declare array for entire problem.
ll pre[100005]; //declare pref array which stores gcd of prefixes.
ll suf[100005]; //declare suf array which stores gcd of suf.

//declare euclid gcd function.
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

//declare solve function which takes array as parameter.
void solve(ll arr[], ll n)
{
    //take input in array arr.
    cout << "Enter elements: ";
    for (ll i = 1; i <= n; i++)
        cin >> arr[i];

    //initialise pref[0]=0 as gcd with 0 doesn't effect
    //the solution and gcd takes two parameter.

    pre[0] = 0;
    //iterate through the array and calculate gcd of prefixes.
    for (ll i = 1; i <= n; i++)
        pre[i] = gcd(pre[i - 1], arr[i]);

    suf[n + 1] = 0; //same as prefix cases.
    //iterate through the suffix array and calculated the suffix gcd.
    for (ll i = n; i >= 1; i--)
        suf[i] = gcd(suf[i + 1], arr[i]);
}

int main()
{
    ll t;

    cout << "Enter number of test cases: ";
    //take input.
    cin >> t;

    while (t--) {
        //take input size of array and queries.
        ll n, q;
        cout << "Enter size of array and queries count: ";
        cin >> n >> q;
        //call solve function.
        solve(arr, n);
        //process queries.
        cout << "Enter queries: ";
        while (q--) {
            ll l, r;
            //take input L and R.
            cin >> l >> r;
            //use pref[L-1] to get gcd of numbers berfore L and use
            //suf[R+1] to get gcd of number from n to R+1.
            cout << "Final Gcd: ";
            cout << gcd(pre[l - 1], suf[r + 1]) << "\n";
        }
    }

    return 0;
}

Output:

Enter number of test cases: 1
Enter size of array and queries count: 3 3
Enter elements: 2 6 9
Enter queries: 1 1
Final Gcd: 3
2 2
Final Gcd: 1
2 3
Final Gcd: 2