Problem 372

[ldesnogu]

The problem says:

M<x≤N, M<y≤N and [x²/y²] are odd

Shouldn't that be:

M<x≤N, M<y≤N and [x²/y²] is odd

[subu]

[flash=]They both are one at the same[/flash]

[TripleM]

It should be 'is', yes.

[hk]

It should be 'is', yes.

Changed.

[petersc]

I am having trouble understanding why my solution works for R(100,10000) and not for R(2000000,1000000000). I am using 64 bit unsigned long variables, which should accommodate 10^18 just fine, any hints?

[AbsoluteConvergence]

I'm having a similar problem, my algorithm checks out for everything I was able to verify by a brute force alternative, but fails for R(2*6^10,10^9), I'm using python so there shouldn't be problems with large numbers. Unfortunately it also took 92 hours to run.

[arechitsky]

i found solution for O( K*log(K) ), where K is about 10⁶, so, it work, but gives wrong answer . It work absolutely correct at R(0,100) (comparing with bruteforce) and gives right answer at R(100,10000), but answer at R(2*10⁶, 10⁹) is not correct. I'm using python 3.2, any hints?

UPD: I tried numpy, other answer, but incorrect too

[Marcus_Andrews]

Always double-check any overflow or precision issues.