問題一覧 > 通常問題

No.3102 floor sqrt xor

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 52
作問者 : shobonvip / テスター : noya2
お気に入りにしたユーザー ProblemId : 11576 / 自分の提出
問題文最終更新日: 2025-04-11 21:21:00
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 464 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。