lazyneuron's blog

Find number of coprime pairs
By lazyneuron, history, 6 years ago, In English

I was stuck in a question from https://icpc.baylor.edu/regionals/finder/mid-central-usa-2018. The problem gives you 4 values a, b, c and d where a <= b and c <= d and b, d <= 10^7. We are supposed to find all ordered pairs (x, y) where a <= x <= b and c <= y <= d. I cannot understand how inclusion-exclusion principle / any other combinatorics can be efficiently used here.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here's a more general version of your problem. It can be solved using Mobius Inversion that is beautifully explained in this blog post. There's also the solution to the problem in the comments section of the post.

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The way I like to do it is to calculate the number of ordered pairs (x, y) such that a ≤ x ≤ b, c ≤ y ≤ d and gcd(x, y) > 1, this is the opposite of co-prime pairs.

What you do is that you start out by counting the number of pairs that have even gcd, then continue with counting the number of pairs which are divisible by 3, then the number of pairs that are divisible by 5 and so on.

Problem is that you've now over-counted as there are pairs with gcd divisible by both 2 and 3, so subtract the number of pairs divisible by 6, and do the same for 10 and so on.

But now you have under-counted as there are pairs with gcd divisible by 2,3 and 5, so add the number of pairs divisible by 30.

And so on ...

This is actually just the inclusion-exclusion principle. Lets think about what we did. For numbers n that contained an odd number of unique prime factors we added the count of all pairs with gcd divisible by n. For numbers n that contains an even number of unique prime factors we subtracted all pairs. For all other n, for example n = 4, we didn't do anything.

So for each n we either use  + ,  -  or 0. There is name for this, it is called the Möbius function μ. Only difference is that it is defined  -  what we want, so lets use  - μ.

Final formula: Number of ordered pairs (x, y) such that a ≤ x ≤ b, c ≤ y ≤ d and gcd(x, y) > 1 is

(# of pairs (x, y) such that their gcd is divisible by n).

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the explanation. Can you explain why non square-free numbers contribute zero to the final count?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Non square-free numbers contribute zero because they never appear in the calculations. You start with the primes, and then you take the products of (different) primes. So you naturally only get square-free numbers.

      → Reply