平时求一个正整数 $x$ 除以 $2$ 的余数,我们可以使用 x%2,也可以使用 x&1,而后者其实是取 $x$ 在二进制表示中最靠右的一位。因此我们发现在二进制下,如果最靠右一位为 $0$,则这个数为偶数。所以,一个数在二进制下末尾 $0$ 的个数即为这个数能被 $2$ 整除的次数。

我们知道,lowbit 函数可取一个数二进制表达式中最低位的1所对应的值。

#define lowbit(y) y&-y

例如,数 $10$ 的二进制表达为 $1010$,那么此函数返回值为 $1010$ 从右往左数第一个 1 出现的位置,即 $2^1=2$。我们发现,此时的 $2$ 正好为长度为 $10$ 的蛋糕被分出的块数。所以我们只要利用 lowbit 函数计算出每块蛋糕被分成的块数,并用前缀和记录切到第 $i$ 块蛋糕时当前蛋糕的总数即可。

由于每次询问的 $x_j$ 单调不减,所以我们可以用上次询问时的总块数继续查询此次询问。

代码:

#include<bits/stdc++.h>
#define int long long
#define lowbit(y) y&-y
using namespace std;
int n,a[200005],lb[200005],f[200005],t,x,i=1;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        lb[i]=lowbit(a[i]);
        f[i]=f[i-1]+lb[i];
    }
    cin>>t;
    while(t--){
        cin>>x;
        for(;i<=n;i++){
            if(f[i]>=x){
                cout<<a[i]/lb[i]<<endl;
                break;
            }
        }
    }
    return 0;
}