C-牛牛要女装_牛客挑战赛37

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

牛妹想要牛牛女装,但是众所周知,女装的开始都是需要一个被逼无奈的理由。所以牛牛现在缺一个机会,因此他对着牛妹立了一个flag(这是不易察觉的阴谋)。

牛牛告诉牛妹如果你能解决我提出的问题,我就当场女装倒立。为了让牛牛顺理成章的女装,牛妹当然必须答应。

这个问题是这样的，给定一个长度为 $n$ 的序列，该序列由初始调用 $\textrm{build}(n, 0, [])$ 生成，其中 $[]$ 代表一个空数组。函数 $\textrm{build}$ 的定义如下。你需要回答 $q$ 次询问,每次询问长度为 $n$ 的序列中,第 $m$ 个数是多少。回答完这 $q$ 个询问牛牛就当场女装,所以大家加油!

function build(n, base = 0, array = []):
    if n == 0
    end function
    
    now = base + (1 << int(log2(n)))
    array.add(now)
    
    if n == 1
    end function
    
    build((1 << int(log2(n))) - 1, base, array)
    build(n - (1 << int(log2(n))), base + (1 << int(log2(n))), array)
    
end function

其中， $\textrm{int(log2(x))}$ 为数学表达式 $\left\lfloor\log_2(x) \right\rfloor$ 的伪代码写法。

输入描述:

第一行一个整数 $q$ 表示你需要回答的询问数量.

接下来每行两个整数 $n,m$ .

输出描述:

对于每个询问回答 $array$ 的第 $m$ 个数是什么.

示例1

输入

复制

2
10 2
5 1

输出

复制

4
4

备注:





本题已于下方时间节点更新，请注意题解时效性：
1. 2025-12-25 优化题面文本，将原图片形式的伪代码用代码的形式展现，同时增加了初始状态的定义。