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!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.