1846E1.md (1982B)
1 Source: https://codeforces.com/problemset/problem/1846/E1 2 3 E1. Rudolf and Snowflakes (simple version) 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 This is a simple version of the problem. The only difference is that in this version $n \le 10^6$. 22 23 One winter morning, Rudolf was looking thoughtfully out the window, watching the falling snowflakes. He quickly noticed a certain symmetry in the configuration of the snowflakes. And like a true mathematician, Rudolf came up with a mathematical model of a snowflake. 24 25 He defined a snowflake as an undirected graph constructed according to the following rules: 26 27 * Initially, the graph has only one vertex. 28 * Then, more vertices are added to the graph. The initial vertex is connected by edges to $k$ new vertices ($k \gt 1$). 29 * Each vertex that is connected to only one other vertex is connected by edges to $k$ more new vertices. This step should be done at least once. 30 31 The smallest possible snowflake for $k = 4$ is shown in the figure. 32 33  34 35 After some mathematical research, Rudolf realized that such snowflakes may not have any number of vertices. Help Rudolf check if a snowflake with $n$ vertices can exist. 36 37 Input 38 39 The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 40 41 Then follow the descriptions of the test cases. 42 43 The first line of each test case contains an integer $n$ ($1 \le n \le 10^6$) — the number of vertices for which it is necessary to check the existence of a snowflake. 44 45 Output 46 47 Output $t$ lines, each of which is the answer to the corresponding test case — "YES" if there exists such $k \gt 1$ for which a snowflake with the given number of vertices can be constructed; "NO" otherwise. 48 49 Example 50 51 Input 52 53 ``` 54 9 55 56 1 57 58 2 59 60 3 61 62 6 63 64 13 65 66 15 67 68 255 69 70 10101 71 72 1000000 73 ``` 74 75 Output 76 77 ``` 78 NO 79 NO 80 NO 81 NO 82 YES 83 YES 84 YES 85 YES 86 NO 87 ```