The upside down A is a set theory symbol which means "for all the elements in the set". So "upside A" 1<=i<=N means "for all i between 1 and N (both inclusive)".

Fun fact: This special test was not there till yesterday. :)

You are correct that 4804 doesnt exist in the list. So instead look at the subset consisting of the first 6 numbers:

15015 10010 6006 4290 2730 2310

There is no integer which divides all of these.

Interestingly, another way to look at this question is to see if there exists a common prime factor amongst all of the entries of the input vector. For instance, in the example above:

15015 6006 10010 48048

are divisible by 1001, but as a consequence they're also divisible by each of the prime factors of 1001 (7, 11, and 13). So you could also check that there is an integer which is not a common prime factor amongst all of the entries of the subset. For the six integers in the example above the prime factors are:

15015 =   3 5 7 11 13
10010 = 2   5 7 11 13
 6006 = 2 3   7 11 13
 4290 = 2 3 5   11 13
 2730 = 2 3 5 7    13
 2310 = 2 3 5 7 11

So you can see that there does not exist a single common integer amongst the prime factorizations of each of these numbers. Note, this is obviously a horribly inefficient way to solve this problem and will probably fail some test cases due to timeouts.

include

int gcd(int a,int b) { if(b==0) return(a); return(gcd(b,a%b)); } int main() { int t,n,i,j,a[110]; scanf("%d",&t); while(t--) { int f=0; scanf("%d",&n); for(i=0;ia[j]) { if(gcd(a[i],a[j])==1) { f=1; goto A; } } else { if(gcd(a[j],a[i])==1) { f=1; goto A; } } } } A: if(f) { printf("YES\n"); } else { printf("NO\n"); } } return(0); }

First, if 1 is an element, then the subset {1} qualifies because there is no integer greater 1 that divides every element of {1}. So assume 1 is not an element. For simplicity, suppose A has three elements: a, b, and c. Clearly, if the gcd of 2 elements in A is 1, say gcd(a, b) = 1, then gcd(a, b, c) must also be one because gcd(a, b, c) = gcd(gcd(a, b), c) = gcd(1, c) = 1. Conversely, let gcd(a, b, c) = 1. Then 1 = gcd(gcd(a,b), c) = gcd(gcd(a,c), b) = gcd(gcd(b,c), a). Obviously if every pair is relatively prime then we are done, so suppose one pair is not relatively prime, say gcd(a, b) != 1. Then this implies that gcd(a, c) = 1 or gcd(b, c) = 1. For suppose on the contrary gcd(a, c) != 1 and gcd(b, c) != 1. Then a = sc for some integer s and b = tc for some integer t, and then 1 = gcd(gcd(a, b), c) = gcd(gcd(sc, tc), c) = c is a contradiction because c cannot be 1 (remember we assumed 1 is not an element of the array). So we've just shown that gcd(A) = 1 if and only if there exists a pair in A that is relatively prime. And the reason why that's important is because computing gcd(a1, a2, ..., an) is O(n) in the number of times we have to compute the gcd of two numbers. [Whereas, as you point out, computing the gcd of every pair in A is O(binomial(n, 2)) = O(n(n-1)/2) = O(n^2).]

This problem has a very clear and straightforward solution in a dozen statements.

Why did he miss read it?

Never mind got it.

Each elements of B are unique.