Algorithm

 problem Link ; https://www.codechef.com/JAN15/problems/GCDQ 

Problem

Read problems statements in Mandarin Chinese and Russian.

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.

Input

  • First line of input contains an integer T denoting number of test cases.
  • For each test case, first line will contain two space separated integers N, Q.
  • 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 of that query.

Constraints

Subtask #1: 40 points

  • 2 ≤ T, N ≤ 100, 1 ≤ Q ≤ N, 1 ≤ A[i] ≤ 105
  • 1 ≤ L, R ≤ N and L ≤ R

Subtask #2: 60 points

  • 2 ≤ T, N ≤ 105, 1 ≤ Q ≤ N, 1 ≤ A[i] ≤ 105
  • 1 ≤ L, R ≤ N and L ≤ R
  • Sum of N over all the test cases will be less than or equal to 106.

Warning : Large IO(input output), please use faster method for IO.

Sample 1:

Input
 
Output
 
1
3 3
2 6 9
1 1
2 2
2 3
3
1
2

Explanation:

Test case 1: The given array is [2,6,9].

  • Query 1: On excluding the range [1,1], the remaining elements are [6,9]. The gcd of 6 and 9 is 3.
  • Query 2: On excluding the range [2,2], the remaining elements are [2,9]. The gcd of 2 and 9 is 1.
  • Query 3: On excluding the range [2,3], the remaining elements are [2]. The gcd of 2 is 2.
acceptedAccepted
3430
total-SubmissionsSubmissions
27308
accuracyAccuracy
14.2

Code Examples

#1 Code Example with C Programming

Code - C Programming

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

void solve()
{
    int n,q;
    cin>>n>>q;
    int a[n+10],fw[n+10],bw[n+10];
    fw[0]=bw[n+1]=0;
    for(int i=1; i < =n; i++)
    {
        cin>>a[i];
    }
    for(int i=1; i < =n; i++)
    {
        fw[i]=__gcd(fw[i-1],a[i]);
    }
    for(int i=n; i>=1; i--)
    {
        bw[i]=__gcd(bw[i+1],a[i]);
    }
    while(q--)
    {
        int l,r;
        cin>>l>>r;
        cout<<__gcd(fw[l-1],bw[r+1])<<endl;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int TC = 1;
    cin >> TC;
    cin.ignore();
    while (TC--) solve();
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
1
3 3
2 6 9
1 1
2 2
2 3

Output

x
–
+
cmd
3
1
2
Advertisements

Demonstration

CodeChef solution GCDQ  - Gcd Queries Codechef solution in C,C++

Previous
CodeChef solution CNDY - Candies Codechef solution in C,C++
Next
CodeChef solution CS2023_GIFT - The Gift Codechef solution in C,C++