PROBLEM LINK:
Author: Sandeep Singh
Tester: Arkapravo Ghosh
Editorialist: Sandeep Singh
DIFFICULTY:
EASY
PREREQUISITES:
GCD
PROBLEM:
You are given an array A of integers of size N . You will be given Q queries. In each query you are giveny 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.
EXPLANATION:
(Please note that I have used 1 based indexing throughout the editorial)
The solutions to this problem makes use of the property of gcd according to which gcd(a,b,c)=gcd(gcd(a,b),c).
We observe that for each query represented by L and R, We have to calculate GCD of gcd(A_1, A_2,...,A_{L-1}) and gcd(A_{R+1},A_{R+2},...,A_N) . We can do so by precalculating a prefix and a suffix gcd subarray.
Let’s define the prefix and suffix array as follows:
prefix_i=gcd(A_1,A_2,....A_i)
suffix_i=gcd(A_N,A_{N-1},....A_i)
Keeping in mind the above-mentioned property of gcds, we observe that the answer to each query is simply gcd of prefix_{L-1} and suffix_{R+1}
The prefix and suffix arrays are also calculated by the use of the above-mentioned property of gcd.
Prefix_i = GCD( Prefix_{i-1} , A_{i} )
Suffix_i = GCD( Suffix_{i+1} , A_i )
Below is the code to build the prefix and suffix arrays in O(N) time complexity.
prefix[0]=suffix[N+1]=0; //base case
for (i=1 ;i<=N; i++)
prefix[i] = GCD (prefix[i-1], arr[i]);
for (int i=N; i>=1 ;i--)
suffix[i] = GCD (suffix[i+1], arr[i]);
Time complexity is O((N+Q)*K) where K is for gcd calculation.
SOLUTIONS:
Setter's Solution
clude <bits/stdc++.h>
#define ll long long int
#define M 1000000007
using namespace std;
int GCD(int a, int b)
{
if (b==0)
return a;
return GCD (b, a%b);
}
void solve(){
int N,Q,i,L,R;
cin>>N>>Q;
int arr[N+2],prefix[N+2],suffix[N+2];
memset(arr,0,sizeof(arr));
memset(prefix,0,sizeof(prefix));
memset(suffix,0,sizeof(suffix));
for(i=1;i<=N;i++)
cin>>arr[i];
for (i=1 ;i<=N; i++)
prefix[i] = GCD (prefix[i-1], arr[i]);
for (int i=N; i>=1 ;i--)
suffix[i] = GCD (suffix[i+1], arr[i]);
while(Q--){
cin>>L>>R;
cout << GCD(prefix[L-1],suffix[R+1]) << endl;
}
}
int main() {
ios_base:: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
//freopen("ip6.in", "r", stdin);
//freopen("op6.out", "w", stdout);
int T ;
cin>>T;
while(T--)
solve();
return 0;
}
Tester's Solution
from math import *
for _ in range(int(input())):
n, q = map(int, input().split())
a = [0] + list(map(int, input().split()))
dpl = [0 for __ in range(n+2)]
dpr = [0 for __ in range(n+2)]
for i in range(1, n+1):
dpl[i] = gcd(dpl[i-1], a[i])
dpr[n-i+1] = gcd(dpr[n-i+2], a[n-i+1])
for __ in range(q):
l, r = map(int, input().split())
print(gcd(dpl[l-1], dpr[r+1]))