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
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 AL, AL+1 … AR. 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:
Prefixi = GCD of A1, A2 … Ai
Suffixi = GCD of AN, AN-1 … Ai
answer to query [L, R], would be GCD of PrefixL-1 and SuffixR+1.
We can calculate prefix and suffix arrays in O(N) if we notice that:
Prefixi = GCD(Prefixi-1, Ai)
Suffixi = GCD(Suffixi+1, Ai)
Pseudo Code for building prefix and suffix arrays:
n,a=input pre[n],suf[n] //base case pre=a 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.
Use segment trees for range gcd queries. But note that a factor of log N will be increased in complexity.