A lot of people have participated and qualified in Qualification Round of Facebook Hacker Cup. Luckily I am also qualified for First Round. Facebook Hacker Cup Qualification Round consisted 3 problems. All of these problems were programmatically easy but tricky. Lots of people made very simple mistakes while solving these problem(including me).

First Problem of the round was:

### Double Squares

A double-square number is an integer

Xwhich 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, givenX, 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}.

InputYou should first read an integer

N, the number of test cases. The nextNlines will containNvalues ofX.## Constraints

0 â‰¤

Xâ‰¤ 2147483647

1 â‰¤Nâ‰¤ 100

OutputFor each value of

X, you should output the number of ways to writeXas the sum of two squares.Example input

5

10

25

3

0

1Example output

1

2

0

1

1

#### Analysis and Solution

This problem was by far the easiest of the lot. But as Facebook title for the problem said â€œ*Too hard for brute force, switching to dp*â€, this problem was almost impossible to be solved with Brute Force.

The strategy I used was quite simple. If we consider M is the given number, and we want to find out x, y such that:

M = x^2 + y^2

So basically weâ€™ll loop from 0 to sqrt(M) and will find out D such that:

D = M â€“ i*i

and if D is square root is an integer then, this number is a double square.

The python code of this problem is:

My acount is temporarily unavalable,what should i do to turn it back?

dear sir,

i will b pleased if u read my ms. i m very sad boy. my girlfriend is cheating with me. he make contact with other boys by using facebook. but i want 2 know about her cheating. in this case u are the only 1 person who can help me. pls sir. help me. i want to hack her facebook account password. pls help me. i m crying all the night. pls get rid of me from the situation. i have no idea about hacking. pls help me.

he account e-mail is

faizah_nishi@yahoo.com

pls help me. i will be grateful in my whole life to you.

lol. comment fail

[…] Double Squares Peg-Game Studious Student […]

Why go all the way up to range(int(sqrt(int(i)))+1): ? Could just count up to half that (i.e. ensuring that your x<=y) so you don't have to divide by 2.