Find number of coprime pairs

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

I was stuck in a question from 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.


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