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.

  • 0
    Thank you for your answer, I will to try read this book)2012-06-05

2 Answers 2

1

If you don't want too involved math and just look at it as an algorithm question, the way to do this would probably be like this:

int upper_bound = ceil (sqrt(N/3)); int count = 0;  for (int i = 0; i < upper_bound; i++) {   int i2 = i * i;   int j = i;   int k = floor (sqrt(N-i2));    while (j <= k) {     int j2 = j * j;     int k2 = k * k;     int sum = i2 + j2 + k2;      if (sum < N) {       j ++;     } else if (sum > N) {       k --;     } else {       count ++;       j ++;     }   } }  return count; 

Number of loop iterations is roughly upper_bound$^2$/2 which is about N/6. Should do it.

  • 0
    Thank, but for $N = 10^9$ O(N) is very slow.2012-06-05
1

Here's a paper Some Formulae... that gives an explicit formula that may be easier to compute.

It also has one for the number of partitions into 2 squares, which you could use in your step 4) if that's easier.

You can consult A000164 and A000161 at OEIS for more references.