| Submit | All submissions | Best solutions | Back to list |
TWOSQ - Two Squares |
Given an integer, how many distinct ways it can be written as the sum of two square integers? The square integers are 0,1,4,9,...
Since addition is commutative, reordered sums (e.g. 0^2 + 5^2 and 5^2 + 0^2) are not distinct and count as just one way.
For example, 50 can be written as a sum of squares in exactly two distinct ways: 1^2 + 7^2 and 5^2 + 5^2.
Input:
An integer N, from 0 to one quadrillion (10^15) inclusive.
Output:
The number of distinct ways N can be written as the sum of squares.
| Example Input 1: | Example Input 2: | Example Input 3: |
3 |
50 |
97682 |
| Example Output 1: | Example Output 2: | Example Output 3: |
0 |
2 |
5 |
| Added by: | Paul Draper |
| Date: | 2012-04-06 |
| Time limit: | 1.107s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
hide comments
|
2012-11-20 12:42:51 Sidharth Gupta
This problem already exists on SPOJ with different constraints or as a variation. http://www.spoj.pl/problems/TWOSQRS/ http://www.spoj.pl/problems/SQUAREV1/ http://www.spoj.pl/problems/SQUA_REV/ I believe it should be moved to tutorial or the constraints should be made harder! 10s is too much! |
|
|
2012-10-24 07:30:30 tantu92
is ter only one test case??? Last edit: 2012-10-24 07:35:44 |
|
|
2012-10-17 15:13:18 gourav
19th ;) |
|
|
2012-10-17 01:56:56 Mitch Schwartz
It would be a nice problem if time limit were decreased and test data were made harder, with multiple test cases per input file. Last edit: 2012-06-16 04:33:21 |
|
|
2012-10-17 01:56:56 :D
Please make the time limit stricter. I got 8s in total with brute force!! |
RSS