Дано целое положительное число $$$x$$$. Обозначим за $$$f(x)$$$ число, образованное переворотом двоичного представления $$$x$$$ без ведущих нулей. Например, если $$$x=12=1100_2$$$, то $$$f(x)=0011_2=3$$$.
Вам дано целое число $$$n$$$. Определите, существует ли такое целое положительное число $$$x$$$, что $$$x \oplus f(x) = n$$$$$$^{\text{∗}}$$$.
$$$^{\text{∗}}$$$Здесь $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$0 \leq n \lt 2^{30}$$$).
Для каждого набора входных данных выведите YES, если существует положительное целое число $$$x$$$, такое что $$$x \oplus f(x) = n$$$, и NO в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
603681011
YESYESYESNOYESNO
В первом случае, когда $$$x=1$$$, $$$f(x)=1$$$, и $$$x \oplus f(x)=0$$$. Таким образом, ответ — YES.
Во втором случае, когда $$$x=2$$$, $$$f(x)=1$$$, и $$$x \oplus f(x)=3$$$. Таким образом, ответ — YES.
В четвертом наборе входных данных можно показать, что не существует $$$x$$$, удовлетворяющего $$$x \oplus f(x)=8$$$, поэтому ответ — NO.
| Codeforces Round 1058 (Div. 2) |
|---|
| Закончено |
