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
coderslegacy:
2018-04-24 02:13:40
strictly use Fermat Theorem costed me 2 TLE
|
|
kkislay20:
2018-01-17 18:02:27
I did the c++ implementation of fermat method but got TLE. Any suggestions would be appreciated. |
|
sandeep_123:
2017-12-14 13:48:24
80 :D !!
|
|
vishesh197:
2017-08-20 12:33:33
use bruteforce with bit of optimization and do it in O(sqrt(n))
|
|
evoiz963:
2017-07-21 11:56:19
brute force
|
|
babur:
2017-06-29 05:39:34
Try using 2 pointer...simple AC in 1 go |
|
prabodh prakash:
2017-05-07 11:40:55
Bad observational skills costed me 3 TLE. I should have tested huge numbers before submitting my solution. Not a brute force solution. |
|
anurag_tangri:
2017-03-30 21:37:24
AC USING BRUTE FORCE :) |
|
rv404674:
2017-03-24 19:38:23
AC in 0.00 using fermat |
|
cake_is_a_lie:
2017-02-15 01:21:07
The given tests have the funny property that they can all pass even when you consider 2 as your only prime number. Sadistic. Cost me a WA because of a super silly mistake. |
Added by: | gawry |
Date: | 2004-06-29 |
Time limit: | 2s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |