No.3088 XOR = SUM
タグ : / 解いたユーザー数 80
作問者 :

問題文
非負整数 $N$ が与えられます。以下の条件を満たす整数の組 $(X,Y)$ として $X\times Y$ が最大となるものを一つ構築してください。(条件を満たす $(X,Y)$ は少なくとも $1$ 組は存在します。)
- $0\le X,Y$
- $X+Y\le N$
- $X \oplus Y = X + Y$
ただし、$\oplus$ はビット毎の排他的論理和を表します。
ビット毎の排他的論理和とは?
$x \oplus y$ は、$x,y$ をそれぞれ二進数に直したのち、各桁について排他的論理和(異なる値なら $1$,同じ値なら $0$)を取ったものです。
例として、 $12\oplus 10 = 1100_{(2)} \oplus 1010_{(2)} = 0110_{(2)} = 6,\ \ 100 \oplus 100 = 0$ です。
$T$ 個のテストケースすべてについて、答えを求めてください。
入力
$T$ $case_1$ $case_2$ $\vdots$ $case_T$
各テストケースは、以下の形式で与えられる。
$N$
制約
- $1\le T \le 2\times 10^5$
- $0\le N \le 10^{18} $
- 入力はすべて整数
出力
$T$ 行出力してください。 $i$ 行目には、テストケース $i$ に対する答えを出力してください。条件を満たすものであれば、どれを出力しても正答とみなされます。
最後に改行してください。
サンプル
サンプル1
入力
3 3 0 271828182845904
出力
2 1 0 0 140737488355328 131090694490576
一つ目のテストケースについて、 $2\oplus 1 = 2+1=3$ であり、条件を満たす $(X,Y)$ として $X\times Y$ が最大になります。
他に $(1,2)$ も正答とみなされます。
与えられる $N$ 及び出力すべき $X,Y$ が $32$ bit整数型に収まらないことがある点に注意してください。(C++を用いる場合、intの代わりにlong longを使用してください。)
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。