Find number of coprime pairs

Revision en1, by lazyneuron, 2019-02-14 09:20:19

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English lazyneuron 2019-02-14 09:20:19 404 Initial revision (published)