0
$\begingroup$

Possible Duplicate:
Number of integer solutions: $x^2 + y^2 + z^2 = N$

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

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

Time limit - 1 second. $N <= 10^9$.

My wrong algorithm:

1)calculate prime numbers (0..sqrt(N))

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

3)for all $A_i$ numbers 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 ~ 1.7 seconds but it is bad.

  • 0
    There is a fast solution to calculating how many solutions do you have to A^2 + B^2 = C Compute the number of solutions for the first few values of C and the try searching on oeis.2012-06-05
  • 0
    Don't forget that integers include negative numbers. So if you solve for all positives, you need to multiply by 8 for all the combinations of negatives which get squared to add to the positive N.2012-06-05
  • 0
    Will finding the `factors` of `N` help in reducing the restrictions on `x`,`y`,`z`?2012-06-05
  • 0
    To LanceH: Thank, I am not forget. To Subs: Thank, I try it, but I can't to see any series.( I read some math paper on this problem, but it is really hard.2012-06-05
  • 0
    Consider that this corresponds to integer coordinates on the surface of a sphere, radius sqrt(N)...2012-06-05

0 Answers 0