| Submit | All submissions | Best solutions | Back to list |
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
| Added by: | gawry |
| Date: | 2004-06-29 |
| Time limit: | 2s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
hide comments
|
||||||||||||||
|
2021-11-04 07:16:29
0.11second O(sqrt(N)) brute force. For the loop, use long long as well instead of int |
||||||||||||||
|
2021-09-11 11:03:16
one solving wd brute force, run your loop till sqrt(n) |
||||||||||||||
|
2021-02-28 18:32:36
But lengthy |
||||||||||||||
|
2021-02-28 18:32:25
It's not tough |
||||||||||||||
|
2020-12-12 11:43:51
can anyone tell me, if one didn't know Fermat's theorem, could they have come up with the solution on their own? If yes, how do you think they would have approached this? |
||||||||||||||
|
2020-07-31 21:02:36
Take care of output, It's "Yes" not "YES. Just wasted 3 hrs on this. Phew. Ac Not in one Go! |
||||||||||||||
|
2020-03-22 16:49:43
@zerodark For test case 0, 0 = 0^2 + 0^2, because 0 is an integer. So output will be "Yes" |
||||||||||||||
|
2020-02-13 07:51:10
For Test case 0 output is NO |
||||||||||||||
|
2019-12-09 15:31:09
Explicit type conversion works well.. |
||||||||||||||
|
2019-11-20 00:24:41
AC with precomputation and binary search!! :) |
||||||||||||||
RSS