#codeifyoucansolve
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.
Example
Input:
1
3 3
2 6 9
1 1
2 2
2 3
Output:
3
1
2
Explanation
For first query, the remaining part of array will be (6, 9), so answer is 3.
For second query, the remaining part of array will be (2, 9), so answer is 1.
For third query, the remaining part of array will be (2), so answer is 2.
Warning : Large IO(input output), please use faster method for IO.
#include<stdio.h>
#define MAX 100000
unsigned long long gcd(unsigned long long x, unsigned long long y){
unsigned long long wk;
if(x<y){ wk=x;x=y;y=wk; }
while(y){
wk = x%y;
x=y;
y=wk;
}
return x;
}
unsigned long long gcd_a(unsigned long long N,unsigned long long n, unsigned long long a[MAX],long long l,long long r)
{
unsigned long long num,i;
if(n==1)
{
if((l-1)>=0)
return a[0];
else
return a[r+1];
}
if(n==2)
{
if((l-1)>=0&&(r+1)<N)
{
return gcd(a[l-1], a[r+1]);
}
else if((l-1)<0&&(r+1)<N)
{
return gcd(a[r+1], a[r+2]);
}
else
return gcd(a[0], a[1]);
}
else
{
if((r+1)>=N)
{
num = gcd(a[0],a[1]);
for(i=2;i<l;i++)
num = gcd(num,a[i]);
return num;
}
else if((l-1)>=0&&(r+1)<N)
{
if(l>1)
{
num = gcd(a[0],a[1]);
for(i=2;i<l;i++)
num = gcd(num,a[i]);
for(i=r+1;i<N;i++)
num = gcd(num,a[i]);
return num;
}
else
{
num = gcd(a[0],a[r+1]);
for(i=r+2;i<N;i++)
num = gcd(num,a[i]);
return num;
}
}
else
{
num = gcd(a[r+1],a[r+2]);
for(i=r+3;i<N;i++)
num = gcd(num,a[i]);
return num;
}
}
}
inline unsigned long long get_input()
{
unsigned long long num=0,sign=1;
char d = getchar_unlocked();
if(d == '-')
sign = -1;
while((d<'0'||d>'9') && d!=EOF&&d!='-')
d = getchar_unlocked();
if(d == '-')
sign = -1, d=getchar_unlocked();
while(d>='0' && d<='9')
{
num=(num<<3)+(num<<1)+(d-'0');
d=getchar_unlocked();
}
return sign*num;
}
int main(void){
unsigned long long T,N,Q,A[MAX],n,num,i;
long long L,R;
T = get_input();
while(T--)
{
N = get_input();
Q = get_input();
i = 0;
while(i<N)
{
A[i] = get_input();
i++;
}
while(Q--)
{
L = get_input();
R = get_input();
n = N-(R-L+1);
num = gcd_a(N,n, A,L-1,R-1);
printf("%llu\n", num);
}
}
return 0;
}
Code N Solve 