1

For reference, I am trying to solve this CSES Problem.

The problem basically states that given up to 10^5 positive integers in the range [1, 10^6], find the number of pairs of those positive integers that are coprime.

After some thought, I've come up with the following 3 ideas that I think may be on the right track, but are each missing something.

Brute-Force Idea: Simply iterate through all O(N^2) pairs of integers in the array, and increment our answer every time the pair of integers has a Greatest Common Divisor of 1. Using the Euclidean Algorithm to find GCDs, we obtain a time complexity of O(N^2logN), but this is too slow since N <= 10^5.

Idea #2 (Sieve of Erathosthenes): I thought that there had to be some significance to all the numbers being bounded by the rather low 10^6 and not something like 10^9 or 10^{18}. Specifically, the bound allows us to create an Extended Sieve of Eratosthenes (basically just a normal sieve except we keep, for each number, the smallest prime number that is a factor of it). However, only comparing the smallest prime factors of 2 numbers is not enough to determine if they're actually coprime (consider 14 and 21), and besides, this still involves testing all pairs of numbers, which is too slow.

Idea #3 (Principle of Inclusion and Exclusion): My most recent idea is that perhaps we can construct, for each prime number in the range [1, 10^6], whichever given numbers are divisible by it. Then, the number of coprime pairs = the total number of pairs (N(N-1)/2) - the number of pairs of prime numbers such that both numbers appear in at least 1 same set, and the last term can be calculated with the PIE's formula. The problem with this is that the Principle involves the intersections of sets, and I have no idea how to calculate these intersections without re-iterating through all integers, not to mention that calculating the various terms in the formula of PIE requires iterating through all subsets of the integers (O(2^N)) - again, this approach seems too inefficient.

Overall, I'm pretty sure that at least one of these ideas is somehow on the right track, but I have been unable to find the missing link to the final solution. Can someone point me in the right direction? Thanks a lot!

Christopher Miller
  • 861
  • 4
  • 9
  • For #2, there's no reason not to include *every* prime that divides z in the sieve entry for z. You can also create an empty set for all the the primes P <=10^6 and then add x_i to the set of every prime that divides x_i. When you are finished with this pass through the x_i you can take the union of all the sets that x_i appears in (one for each prime that divides it). This is the set of every x_j that x_i is **not** co-prime to, thus the complement of this set is the set you want. – President James K. Polk Jul 10 '21 at 19:32

0 Answers0