No.3102 floor sqrt xor
Problem Statement
You are given a non-negative integer $N$. Determine whether there exists a non-negative integer $k$ such that $\lfloor \sqrt{k} \rfloor \oplus k = N$, and if one exists, find $1$ such integer.
Here, $\oplus$ denotes bitwise xor. Also, for a real number $x$, $\lfloor x \rfloor$ denotes the largest integer not exceeding $x$. For example, $\lfloor 3.14 \rfloor = 3, \lfloor 4 \rfloor = 4$.
You are given $T$ test cases; solve each of them.
Constraints
- All input values are integers
- $1 \le T \le 100$
For each test case,
- $0 \le N \lt 2^{60}$
Input
$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$
Here, $\text{case}_i$ $(1\le i \le T)$ represents the $i$-th test case. Each test case is given in the following format.
$N$
Output
Print $T$ lines. On the $i$-th line $(1\le i\le T)$, for $N$ of the $i$-th test case, if there exists a non-negative integer $k$ such that $\lfloor \sqrt{k} \rfloor \oplus k = N$, print $1$ value of $k$; if no such non-negative integer $k$ exists, print -1.
Sample
Sample 1
Input
8 1 2 10 0 11 12 998244353 1152921504606846975
Output
-1 3 9 0 -1 15 998275946 1152921503533105152
For test case $1$, no non-negative integer satisfies $\lfloor \sqrt{k} \rfloor \oplus k = 1$.
For test case $2$, $\lfloor \sqrt{3} \rfloor \oplus 3 = 1 \oplus 3 = 2$, so print $3$.
For test case $3$, there are non-negative integers satisfying $\lfloor \sqrt{k} \rfloor \oplus k = 10$, namely $k=8$ and $k=9$, which are $2$ in total; you may print either of them.
For test case $4$, there are non-negative integers satisfying $\lfloor \sqrt{k} \rfloor \oplus k = 0$, namely $k=0$ and $k=1$, which are $2$ in total; you may print either of them.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
noya2