問題一覧 > 通常問題

No.3088 XOR = SUM

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 80
作問者 : yuusaan / テスター : 👑 amentorimaru
0 ProblemId : 11822 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-04-04 10:24:05

問題文

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