| Submit | All submissions | Best solutions | Back to list |
POLCONST - Constructible Regular Polygons |
The investigation of which regular polygons can be constructed only with compass and straight-edge is a classical problem in mathematics. Triangle, square, hexagon can easily be constructed, but, can we construct a regular heptagon? It was the German mathematician Gauss (1777-1855) who first proved that one could construct a 17-sided regular polygon and later, in one the of the most beautiful math works of all time (Disquisitiones Arithmeticae, 1798), he gave sufficient conditions to decide which regular polygons can be constructed.
Input
In the first line, an integer T < 50000 representing the number of test cases; then, T integer numbers representing the number of sides of a non-degenerated regular polygon, up to 1000000 (106).
Output
Print “Yes” if the regular polygon can be constructed with compass and straight-edge or “No” otherwise.
Example
Input: 5 5 6 7 8 9 Output: Yes Yes No Yes No
| Added by: | campos20 |
| Date: | 2013-12-23 |
| Time limit: | 1s-2s |
| Source limit: | 1000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | Classical math. |
hide comments
|
2015-08-22 21:30:36 shantanu tripathi
done using bs :D |
|
|
2015-07-29 15:51:19 [Mayank Pratap]
Revised many things and learnt some new maths ... :) |
|
|
2015-05-30 06:02:32 Mani Soni
learned about fermat numbers by this question..Good question |
|
|
2015-03-23 18:47:43 TUSHAR SINGHAL
my 50th ac :-) yeahhhhhhhhhhhhh |
|
|
2014-01-28 13:45:00 praveen123
I liked the problem very much. But I believe that constraints are really weak here. The problem can be easily solved even if n <= 10^18. ---------- I've chosen 10^6 to avoid problem setter mistakes (like wrong answer in the output file). I tested all the number multiple times, coded official solution in various ways and 3 languages. Specifically, I wanted all the numbers to be smaller than 65537^2. Anyways, thank you for your observation! I'll take that in consideration if I set new problems. Alexandre Last edit: 2014-01-22 11:47:09 |
|
|
2014-01-28 13:45:00 Alexandre Henrique Afonso Campos
The "non-degenerated" part is just a fancy way to say that all the numbers are bigger than 2 (n>2, because the minimum number of sides for a polygon like this is 3). @Tanmay The test cases are okay. You might wanna try the following in your first submission: Input 1 65537 Output Yes Last edit: 2013-12-26 20:37:48 |
RSS