0%

Problem 372

Pencils of rays

Let R(M, N) be the number of lattice points (x, y) which satisfy M<x≤N, M<y≤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·106, 109).

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

：$\lfloor x \rfloor$表示下取整函数。