EOJ 2020 January race E-number transformation

Portal

Cuber QQ Brushing EOJ Water question on , A topic he is working on is like this .

Given a positive integer x ：

If x If it's an odd number , Then it changes into x−1 ;
If x If it's even , Then it changes into x * 2 .
Perform this operation so repeatedly , until x Turn into 1 .

Obviously, this is for Cuber QQ It's too simple . therefore Cuber QQ According to this invention, a sequence , It is called the changing sequence , x - Changing sequence refers to , from x As the beginning of change , It changes until 1 The sequence formed , for example 7 - The changing sequence is {7,6,3,2,1} ; 10 - The changing sequence is {10,5,4,2,1} .

And now Cuber QQ Write all on the paper 1 To n Variable sequence , He counted the number of times each number appeared in these sequences , For example, when n=4 When , The four sequences are [1]={1},[2]={2,1},[3]={3,2,1},[4]={4,2,1} , be Count 1 There is 4 Time , Count 2 There is 3 Time , Count 3 There is 1 Time , Count 4 There is 1 Time .

Now? Cuber QQ Want to know the maximum number x Satisfy x In all 1 To n At least in the changing sequence k Time .

Input format
The first line contains an integer T(1≤T≤104) , Represents the number of data groups .

For each set of data, there are two integers n,k(1≤k≤n≤1018) , The meaning is as stated in the title .

Output format
For each set of data , Output an integer on a line to represent the answer .

Examples
input
4
4 1
4 2
4 3
4 4
output
4
2
2
1

Title x - How to generate variable sequences , In the sense of binary , does ：

• At the end of it is 1 , Has become a 0 ;
• At the end of it is 0 , Then remove it directly .

For each number x Come on , It can change once by itself , It can also be obtained by some larger number changes .
In a nutshell , When x When it's even ,x Will be x+1 and 2 * x Change once , When x When it is an odd number, it will be 2 * x Change once .

that , It's easy to find , If odd numbers and even numbers are considered independently , It satisfies monotonicity .
So we consider dichotomy of odd and even numbers to determine the maximum value , Then take the larger of the two as the answer .

First , We consider for each k, It can change into x Of k ∗ x + b Maximum number of .

k	1	2	4	m
x Is odd	x	2x,2x+1	4x,4x+1,4x+2,4x+3	m-1+1 individual
x It's even	x,x+1	2x,2x+1,2x+2,2x+3	4x,4x+1,4x+2…4x+7	2m-1+1 individual

consider x yes ∈ [1,n], So for each k, It can change into x Maximum number of ：
$$\begin{gathered} xyesp.Count：min(n-k\ast x,k-1)+1 \\ xyesaccidentallyCount：min(n-k\ast x,2\ast k-1)+1 \end{gathered}$$
Then we can get the recursive function ：
Quadratic growth , should T No. .

ll sol(ll x,ll k)
{
    
    if(x*k>n)   return 0;
    ll le = n - x*k;
    if(x&1) return min(le,k-1) + 1 + sol(x,k<<1);
    else    return min(le,k*2-1) + 1 + sol(x,k<<1);
}

Then you can count even two points , Compare odd numbers , Take the maximum value .

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
#include<queue>
#include<utility>
#include<set>
#include<stack>
#include<string>
#include<vector>
#define ll long long
#define llu unsigned long long
using namespace std;
const int maxn = 100010;
ll n;
ll sol(ll x,ll k)
{
    
    if(x*k>n)   return 0;
    ll le = n - x*k;
    if(x&1) return min(le,k-1) + 1 + sol(x,k<<1);
    else    return min(le,k*2-1) + 1 + sol(x,k<<1);
}
int main(void)
{
    
    int T;
    ll k;
    scanf("%d",&T);
    while(T--){
    
        scanf("%lld%lld",&n,&k);
        ll le = 0,ri = (n+2)>>1;
        ll mid;
        while(ri-le>1){
    
            mid = (le+ri)>>1;
            ll p = sol(mid<<1,1);
            if(p<k)    ri = mid;
            else    le = mid;
        }
        ll lp = sol(le<<1|1,1);
        if(lp>=k)   printf("%lld\n",le<<1|1);
        else    printf("%lld\n",le<<1);
    }
    return 0;
}