Help required in a problem

Правка en1, от pop3, 2020-08-01 15:34:55

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!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский pop3 2020-08-01 15:34:55 475 Initial revision (published)