January 8, 2011

Hacker Cup - Problem #1 - Double Squares

Into the next one. I’m going to save the second one for last because after a brief glance it seems to be the most difficult from a logic context.

Again, straight from the FB:

———————-

Double Squares

A double-square number is an integer X which can be expressed as the sum of two perfect squares. For example, 10 is a double-square because 10 = 3^2 + 1^2. Your task in this problem is, given X, determine the number of ways in which it can be written as the sum of two squares. For example, 10 can only be written as 3^2 + 1^2 (we don’t count 1^2 + 3^2 as being different). On the other hand, 25 can be written as 5^2 + 0^2 or as 4^2 + 3^2.

Input

You should first read an integer N, the number of test cases. The next N lines will contain N values of X.

Constraints

0 ≤ X ≤ 2147483647

1 ≤ N ≤ 100

Output

For each value of X, you should output the number of ways to write X as the sum of two squares.

Example Input

5
10
25
3
0
1

Example Output

1
2
0
1
1

————————

My gut tells me the solution is pretty easy, you just need to make sure and read the invisible emphases on the constraints line. 

X may equal 0.

AND

X may be as large as 2147483647

The first part of the constraint means that every integer input that is itself a square will have AT LEAST its square root + 0^2 as a sum. 

They explicitly point this out to you in the problem statement:

“On the other hand, 25 can be written as 5^2 + 0^2 or as 4^2 + 3^2.”

The second part of the constraint implies that we could be squaring an awful lot of numbers to brute force this thing through to completion. 

I’m going to start by accounting for the first constraint and solving the sample data set, which should be fast and easy.

Just take every combination of numbers less than the one provided in a given line of input. Now, multiply each of the two per set by themselves and sum the products. If it equals the value from the input, then that counts as a match. Do your book keeping.

Don’t forget to account for zeroes and ones. 

That’s it.

Now, mock up some test data to match the worst case scenario and see how fast it performs. I’m about to do the same, myself.

•