310526: CF1846E2. Rudolf and Snowflakes (hard version)
Description
This is the hard version of the problem. The only difference is that in this version $n \le 10^{18}$.
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 whether a snowflake with $n$ vertices can exist.
InputThe 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^{18}$) — the number of vertices for which it is necessary to check the existence of a snowflake.
OutputOutput $t$ lines, each of which is the answer to the corresponding test case — "YES" if there exists such $k > 1$ that a snowflake with the given number of vertices can be constructed; "NO" otherwise.
ExampleInput9 1 2 3 6 13 15 255 10101 1000000000000000000Output
NO NO NO NO YES YES YES YES NO
Input
题意翻译
询问 $T$ 次：是否存在一个满 $k$（$k\ge 2$） 叉树节点数恰好为 $n$，且深度至少为 $2$。Output
这个问题是“Rudolf和雪花”难题的困难版本。在这个版本中，唯一的区别是n≤10^18。一个冬天的早晨，Rudolf在窗前若有所思地观察着飘落的雪花，他很快注意到雪花配置中存在一定的对称性。作为一个真正的数学家，Rudolf提出了一个雪花的数学模型。他将雪花定义为一个根据以下规则构建的无向图：最初，图只有一个顶点。然后，图的初始顶点通过边连接到k个新顶点（k>1）。每个只连接一个其他顶点的顶点通过边连接到k个新顶点。这一步至少要做一次。对于k=4，最小的可能的雪花如图所示。经过一些数学研究，Rudolf意识到这样的雪花可能不存在任何数量的顶点。帮助Rudolf检查是否存在具有n个顶点的雪花。
输入输出数据格式：
输入：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
然后是测试用例的描述。
每个测试用例的第一行包含一个整数n（1≤n≤10^18）——需要检查雪花存在性的顶点数。
输出：
输出t行，每行是对应测试用例的答案——如果存在这样的k>1，使得可以构建具有给定顶点数的雪花，则输出“YES”；否则输出“NO”。题目大意： 这个问题是“Rudolf和雪花”难题的困难版本。在这个版本中，唯一的区别是n≤10^18。一个冬天的早晨，Rudolf在窗前若有所思地观察着飘落的雪花，他很快注意到雪花配置中存在一定的对称性。作为一个真正的数学家，Rudolf提出了一个雪花的数学模型。他将雪花定义为一个根据以下规则构建的无向图：最初，图只有一个顶点。然后，图的初始顶点通过边连接到k个新顶点（k>1）。每个只连接一个其他顶点的顶点通过边连接到k个新顶点。这一步至少要做一次。对于k=4，最小的可能的雪花如图所示。经过一些数学研究，Rudolf意识到这样的雪花可能不存在任何数量的顶点。帮助Rudolf检查是否存在具有n个顶点的雪花。 输入输出数据格式： 输入： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 然后是测试用例的描述。 每个测试用例的第一行包含一个整数n（1≤n≤10^18）——需要检查雪花存在性的顶点数。 输出： 输出t行，每行是对应测试用例的答案——如果存在这样的k>1，使得可以构建具有给定顶点数的雪花，则输出“YES”；否则输出“NO”。