HS09EQ - Diophantine equation
Sometimes solving a Diophantine equation is very hard. But, for example, the equation a+b2+c3+d4=n has a trivial solution for every value of n. Your task is to determine the number of solutions of the equation for each given n, assuming that in the equation all the values a, b, c and d are non-negative integers.
Input
The first line of input contains an integer T, representing the number of test cases (T<20000).
The following T lines contain one non-negative integer n each, where n < 109.
Output
Output T lines, each containing the number of solutions of the respective equation for n.
Example
Input: 5 0 1 10 100 1000 Output: 1 4 19 148 1476
hide comments
|
abhinav_jain02:
2019-06-13 16:21:08
Just brute force.
|
|
Bhavik:
2013-12-24 20:42:40
finally...:)) |
|
anurag garg:
2013-12-24 15:14:31
very good question...
|
|
Mitch Schwartz:
2012-12-09 14:13:25
As far as I can tell, current scoring system is: There are 5 input sets, and for each you get 2 points for AC, 0 points otherwise. Total score is sum of individual ones. |
|
Aditya Pande:
2012-12-09 14:13:25
please define the scoring
|
|
|
Mitch Schwartz:
2012-12-09 14:13:25
Thanks, although that introduces another (potential) issue - the problem is now scored as if it is a challenge problem, even though it is in classical section. It's some peculiarity of SPOJ system. See for example zukow's comment on NUMGUESS. (The reverse is also true -- a problem in challenge section will count as classical if it has binary scoring set.) Last edit: 2012-11-29 00:49:27 |
|
Robert Gerbicz:
2012-12-09 14:13:25
OK, changed the judge to maximize the score. |
|
|
Mitch Schwartz:
2012-12-09 14:13:25
I probably also should have mentioned: For "accepted" solutions that fail some input sets, the time for the failed sets is not added to total time, so those submissions can seem fast when in fact they are wrong or too slow. Would it be possible to change to standard judge? Or I think changing the "limit" to 10 instead of 1 might have the same effect. And of course a rejudge would be appreciated. Last edit: 2012-10-20 18:29:35 |
|
|
Mitch Schwartz:
2012-12-09 14:13:25
The constraints are VERY misleading. I spent a long time trying to find a faster algorithm, when my initial idea was fine.
|
| Added by: | Robert Gerbicz |
| Date: | 2009-09-07 |
| Time limit: | 1s-4s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 C++ 4.3.2 ERL JS-RHINO NODEJS PERL6 SCALA |
| Resource: | High School Programming League |
RSS