Given array of n elements. Find the number of pairs i, j (1 ≤ i < j ≤ n) such that gcd(ai,aj) = 1.
Constraints are: 1 ≤ N ≤ 30000, 1 ≤ a i ≤ (10^8). TL = 0.6s
One user has explained the solution here but I am not able to understand how subsets are used in the solution and the time complexity part.
If someone can please explain, it would be of much help. Thanks in advance!