WA in E - Coprime in Atcoder ABC-177

Question Link - E - Coprime
My solution - CUJSSt - Online C++0x Compiler & Debugging Tool - Ideone.com

If the gcd of the array is not equal to 1, then the answer is ‘not co-prime’.

If all the pairs are co-prime then the product of all the elements will be equal to lcm of the array and gcd will be 1, and in such cases answer will be ‘pairwise coprime’.

If the gcd of the array is 1 but the lcm of the array is not equal to the product of all the elements in array then it will be ‘setwise coprime’.

My solution is giving WA on 6 sub tasks and passing rest of the cases.

watch this:

1 Like

For checking pairwise co prime, insert factors of each number except 1 in a set/map and check if duplicates exist.
If there exists any duplicate then this means that there exists 2 numbers which have common factor of GCD as this duplicate number, so it is not pair wise co prime ,
It would take O(n*sqrt(n)) time to do this
To check setwise co prime, calculate the gcd of array by calculating gcd of consecutive elements, and check if it is 1 or not, This would take O(nlogn)
Hope it helps

4 Likes