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
BOND:
2013-01-25 08:04:00
naive fermat's won't pass... |
|
saket diwakar:
2013-01-16 16:57:41
easy one....:) |
|
Philipp Heeg:
2012-12-25 16:53:30
2888 = 2 38² |
|
gourav:
2012-12-06 16:47:53
awesome things i have learnt while doing this single question...hats off my mathematicians.. :-) |
|
750:
2012-11-25 01:01:38
2888 ?¡?¡?¡
|
|
Asheesh Ranjan:
2012-10-12 15:46:58
<snip>
|
|
Panagiotis Kostopanagiotis:
2012-09-08 18:25:11
O(K*sqrt(N)) but i get TLE error, i think it's the optimal solution :/ |
|
dev2:
2012-08-14 08:30:50
how 2888 is written in form of sum of the square of two number ?plzz explain...
|
|
Ishan Bhatt:
2012-05-18 15:42:45
is everyone using the prime factorization method?..mine is a O(sqrt(n)) algorithm, but still giving TLE |
|
Darky:
2012-03-21 20:38:01
I'm getting a TLE in JAVA! |
Added by: | gawry |
Date: | 2004-06-29 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |