Rudolf and Snowflakes (simple version) (Codeforces 1846E1)
Tags: Math, brute force

This is a simple version of the problem. The only difference is that in this version $$$n \le 10^6$$$.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.He defined a snowflake as an undirected graph constructed according to the following rules:   Initially, the graph has only one vertex.  Then, more vertices are added to the graph. The initial vertex is connected by edges to $$$k$$$ new vertices ($$$k > 1$$$).  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. The smallest possible snowflake for $$$k = 4$$$ is shown in the figure.  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.

Input: The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.Then follow the descriptions of the test cases.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.

Output: Output $$$t$$$ lines, each of which is the answer to the corresponding test case — "YES" if there exists such $$$k > 1$$$ for which a snowflake with the given number of vertices can be constructed; "NO" otherwise.


Sample Inputs:
9
1
2
3
6
13
15
255
10101
1000000

Sample Outputs:
NO
NO
NO
NO
YES
YES
YES
YES
NO

Solution (Python):
import sys
input = sys.stdin.readline
s = set()
for i in range(2, 1000):
    count = 1 + i + i ** 2
    for j in range(3, 20):
        if count <= 10 ** 6:
            s.add(count)
            count += i ** j
        else:
            break
for _ in range(int(input())):
    n = int(input())
    if n in s:
        sys.stdout.write('YES' + '\n')
    else:
        sys.stdout.write('NO' + '\n')

Solution (Python):
import sys
input = sys.stdin.readline

def cout(j):
    return sys.stdout.write(str(j) + '\n')
t = int(input())
mp = {}
num = 7
i = 2
while num <= 1000000:
    mp[num] = i
    k = i * i
    num = 1 + i + i * i
    a = num
    while a <= 1000000:
        mp[a] = k
        k *= i
        a += k
    i += 1
for _ in range(t):
    n = int(input())
    if n in mp:
        cout('YES')
    else:
        cout('NO')

Solution (Python):
import sys
input = sys.stdin.readline

def cout(j):
    return sys.stdout.write(str(j) + '\n')
t = int(input())
mp = {}
num = 7
i = 2
while num <= 10000000:
    mp[num] = i
    k = i * i
    num = 1 + i + i * i
    a = num
    while a <= 1000000:
        mp[a] = k
        k *= i
        a += k
    i += 1
for _ in range(t):
    n = int(input())
    if n in mp:
        cout('YES')
    else:
        cout('NO')