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!