Pencils of rays

Published on Saturday, 18th February 2012, 01:00 pm; Solved by 350;
Difficulty rating: 60%

Problem 372

Let $R(M, N)$ be the number of lattice points $(x, y)$ which satisfy $M\!\lt\!x\!\le\!N$, $M\!\lt\!y\!\le\!N$ and $\large\left\lfloor\!\frac{y^2}{x^2}\!\right\rfloor$ is odd.
We can verify that $R(0, 100) = 3019$ and $R(100, 10000) = 29750422$.
Find $R(2\cdot10^6, 10^9)$.

Note: $\lfloor x\rfloor$ represents the floor function.