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 |
hide comments
|
Sidharth Gupta:
2012-11-20 12:42:51
This problem already exists on SPOJ with different constraints or as a variation.
|
|
tantu92:
2012-10-24 07:30:30
is ter only one test case??? Last edit: 2012-10-24 07:35:44 |
|
gourav:
2012-10-17 15:13:18
19th ;) |
|
Mitch Schwartz:
2012-10-17 01:56:56
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 |
|
:D:
2012-10-17 01:56:56
Please make the time limit stricter. I got 8s in total with brute force!! |
| 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 |
RSS