/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 625 点
問題文
L\le R を満たす正整数 L,R が与えられます。
以下の条件を満たす長さ R-L+1 の正整数列 A=(A_L,A_{L+1},\ldots,A_R) を良い整数列と呼びます：
- L\le i < j\le R を満たすすべての整数の組 (i,j) に対し、A_i = A_j ならば \operatorname{popcount}(i)<\operatorname{popcount}(j) が成り立つ。
良い整数列 A=(A_L,A_{L+1},\ldots,A_R) 全てに対する \max(A_L,A_{L+1},\ldots,A_R) の最小値を求めてください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
\operatorname{popcount} とは？
非負整数 x について \operatorname{popcount}(x) とは、x を 2 進法で表記したときの 1 の個数です。 より厳密には、非負整数 x について \displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace) が成り立っているとき \displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i です。
例えば、13 を 2 進法で表記すると1101 なので、 \operatorname{popcount}(13)=3 となります。
制約
- 1\le T\le 10^4
- 1\le L \le R\le 10^{18}
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
L R
出力
T 行出力せよ。
i 行目 (1\le i\le T) には、i 番目のテストケース \text{case}_i に対する答えを出力せよ。
入力例 1
5 3 6 1 1 2 15 100 10000000 514284786278117031 620546740167642909
出力例 1
3 1 6 1636985 11375123021856567
1 番目のテストケースについて考えます。
(A_3,A_4,A_5,A_6)=(1,2,2,3) は良い整数列で、\max(A_3,A_4,A_5,A_6)=3 となります。
\max(A_3,A_4,A_5,A_6) < 3 を満たす良い整数列は存在しないので、1 行目には 3 を出力してください。
Score : 625 points
Problem Statement
You are given positive integers L and R satisfying L\le R.
A sequence of positive integers A=(A_L,A_{L+1},\ldots,A_R) of length R-L+1 satisfying the following condition is called a good integer sequence:
- For every pair of integers (i,j) satisfying L\le i < j\le R, if A_i = A_j, then \operatorname{popcount}(i)<\operatorname{popcount}(j).
Find the minimum value of \max(A_L,A_{L+1},\ldots,A_R) over all good integer sequences A=(A_L,A_{L+1},\ldots,A_R).
You are given T test cases; solve each of them.
What is \operatorname{popcount}?
For a non-negative integer x, \operatorname{popcount}(x) is the number of 1's when x is written in binary. More precisely, when a non-negative integer x satisfies \displaystyle x=\sum _ {i=0} ^ \infty b _ i2 ^ i\ (b _ i\in\lbrace0,1\rbrace), \displaystyle\operatorname{popcount}(x)=\sum _ {i=0} ^ \infty b _ i.
For example, 13 written in binary is1101, so \operatorname{popcount}(13)=3.
Constraints
- 1\le T\le 10^4
- 1\le L \le R\le 10^{18}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format.
L R
Output
Output T lines.
The i-th line (1\le i\le T) should contain the answer for the i-th test case \text{case}_i.
Sample Input 1
5 3 6 1 1 2 15 100 10000000 514284786278117031 620546740167642909
Sample Output 1
3 1 6 1636985 11375123021856567
Consider the first test case.
(A_3,A_4,A_5,A_6)=(1,2,2,3) is a good integer sequence, and \max(A_3,A_4,A_5,A_6)=3.
There is no good integer sequence with \max(A_3,A_4,A_5,A_6) < 3, so output 3 on the first line.