2
$\begingroup$

Help me please with some ideas to find number of integer solutions.

$x^2 + y^2 + z^2 = N$

Time limit - $1$ second, $N \leq 10^9$.

My wrong algorithm:

1) Calculate prime numbers on $(0,\sqrt{N})$

2) Compute $\sqrt{N}$ numbers $A_i = N-z^2, z = \sqrt{N}$.

3) For all $A_i$ check that it not include primes $4k+3$ in odd powers.

4)Find answer for each $A_i$ with brute force.

Running time of algorithm $\approx 1.7$ seconds but it is bad.

  • 1
    Do you know any character theory? If you do there is a simple method in Ireland and Rosen's [excellent book](http://www.amazon.ca/Classical-Introduction-Modern-Number-Theory/dp/038797329X/ref=sr_1_1?ie=UTF8&qid=1338908510&sr=8-1).2012-06-05
  • 0
    Thank, but I don't know character theory. Is it really need for solving this problem ?2012-06-05
  • 0
    I'm sure there are probably other methods. This is the one I know though. Sorry.2012-06-05
  • 0
    Thank you for your answer, I will to try read this book)2012-06-05

2 Answers 2