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. 02 + 52and 52 + 02) 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: 12 + 72 and 52 + 52.
Input
An integer N, from 0 to one quadrillion (1015) 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