| Submit | All submissions | Best solutions | Back to list |
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
| 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 |
hide comments
|
2019-06-13 16:21:08
Just brute force. Use sqrt() to avoid TLE. |
|
|
2013-12-24 20:42:40 Bhavik
finally...:)) |
|
|
2013-12-24 15:14:31 anurag garg
very good question... pure logic...and maths |
|
|
2012-12-09 14:13:25 Mitch Schwartz
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. |
|
|
2012-12-09 14:13:25 Aditya Pande
please define the scoring score=? edit thanks mitch Last edit: 2012-12-01 18:38:45 |
|
|
2012-12-09 14:13:25 Mitch Schwartz
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 |
|
|
2012-12-09 14:13:25 Robert Gerbicz
OK, changed the judge to maximize the score. |
|
|
2012-12-09 14:13:25 Mitch Schwartz
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 |
|
|
2012-12-09 14:13:25 Mitch Schwartz
The constraints are VERY misleading. I spent a long time trying to find a faster algorithm, when my initial idea was fine. Also, there's an issue with judging: AC can be given even if some cases fail, as shown when clicking on "accepted". (I disqualified those submissions.) Last edit: 2012-10-13 22:26:38 |
RSS