TWOSQRS - Two squares or not two squares
Given integer n decide if it is possible to represent it as a sum of two squares of integers.
Input
First line of input contains one integer c <= 100 - number of test cases. Then c lines follow, each of them consisting of exactly one integer 0 <= n <= 10^12.
Output
For each test case output Yes if it is possible to represent given number as a sum of two squares and No if it is not possible.
Example
Input: 10 1 2 7 14 49 9 17 76 2888 27 Output: Yes Yes No No Yes Yes Yes No Yes No
hide comments
Steven:
2012-03-18 08:30:50
Sigh, why is SPOJ so slow... |
|
Albert Chen:
2012-01-03 06:38:49
O(sqrt(n)) is no problem, but naive algorithm will fail. |
|
Atanu:
2011-11-12 05:40:26
Please tell me if a better algo exists...I am using O(sqrt(n)) |
|
Mukul:
2011-10-19 18:07:13
ufff....TLE...:(:(
|
|
Nitin Sharma:
2011-10-01 21:03:09
Accepted when changed cin,cout to scanf and printf !! |
|
sandeep aggrawal:
2011-07-18 19:34:06
EDIT : READ note number 1. Last edit: 2011-08-19 14:46:36 |
|
Angel:
2011-06-24 03:13:25
I have the same problem with atanu, can u check for mine. |
|
~:
2011-06-05 16:12:12
@atanu go for fermat's theorem.......... |
|
Atanu:
2011-06-05 10:42:27
Pawel Gawrychowski...please check!!!!!!! |
|
Atanu:
2011-06-05 10:41:49
gives TLE...wen i run it it runs in less than half a sec.....
|
Added by: | gawry |
Date: | 2004-06-29 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |