Given n, you are going to count how many different 4-tuple integer solutions (a, b, c, d) satisfying a2+b2+c2+d2=n?
Note that (1,0,0,0) is different to (0,1,0,0) and is also different to (-1,0,0,0).
There are several test cases, for each test case, n is given in a line. The input is terminate by a single 0.
For each test case, please output the desired answer.
1 2 0
8 24
This series of homework are all problems with ungiven input size! It is (at least the original aim of it is) to enable us to acutally think about a problem from scratch, without the "additional informations" implicated by a specific given problem size.
Of course, we do hope it'd be a rather fun experience, since in real life problems often we do not know whether a problem exhibits an efficient algorithm or is even solvable!!
Anyway, the input size, though not specified, will be "reasonable". That is, if the optimal algorithm is O(n3), then n would be something like 300, if O(nlgn), then perhaps 200000.. etc. Also if values are not otherwise specified, they could be expected to be for example, int.
Migrated from old NTUJ.
Jacobi's four-square thm
| No. | Testdata Range | Score |
|---|