自动搬运

查看原文

来自洛谷，原作者为

	gzlinzy Vn

搬运于2025-08-24 22:36:28，当前版本为作者最后更新于2022-02-18 22:56:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

平时求一个正整数 $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;
}