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

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