No.3624 Product
loop0919
yuusaan
ぽえ問題文
非負整数 $L, R ~ (L \leq R)$ が与えられます。
非負整数 $a, b$ が以下の条件をすべて満たすとします。ここで、 $\mathrm{AND}$ はビットごとの論理積を表します。
- $L \leq a, b \leq R$
- $a ~ \mathrm{AND} ~ b = 0$
このとき、 $a \times b$ としてあり得る最大値を求めてください。ただし、このような $a, b$ が存在しない場合 -1 と出力してください。
$T$ 個のテストケースが与えられるので、それぞれについて答えてください。
ビットごとの論理積 $\mathrm{AND}$ とは（クリックで開く）
非負整数 $x, y$ のビットごとの論理積 $x ~ \mathrm{AND} ~ y$ は以下のように定義されます。
- $x ~ \mathrm{AND} ~ y$ を二進表記したときの $2^k ~ (k \ge 0)$ の位の数は、$x, y$ を二進表記したときの $2^k$ の位のうち両方が $1$ であれば $1$ 、そうでなければ $0$ である。
例えば、 $3 ~ \mathrm{AND} ~ 5 = 1$ となります。（二進表記をすると $011 ~ \mathrm{AND} ~ 101 = 001$ です。）
制約
- $1 \leq T \leq 10^5$
- $0 \leq L \leq R \leq 10^9$
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
各テストケースは以下の形式で与えられる。
$L$ $R$
出力
各テストケースについての答えを順に改行区切りで出力せよ。
サンプル
サンプル1
入力
4 1 4 8 15 45 123 0 1000000000
出力
12 -1 4032 288230375614840832
$1$ 番目のテストケースについて、たとえば $(a, b) = (3, 4)$ は問題文中の条件を満たします。
- $3 ~ \mathrm{AND} ~ 4 = 0$ （二進表記で $011 ~ \mathrm{AND} ~ 100 = 000$ となる）
実は、このときの $a \times b = 12$ は最大値を取ります。
$2$ 番目のテストケースについて、 $8$ 以上 $15$ 以下の整数 $a, b$ であって $a ~ \mathrm{AND} ~ b = 0$ となるような $a, b$ は存在しません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。