C. Test Generator
题意
题目的意思大致是给我们 s 和 m ,要求我们构造一个序列,这个序列需要满足以下两个条件:1.所有元素的和等于 s。2. 每个元素与上 m 都等于其本身。即


最后要求我们输出最小的序列长度 n 。
思路
既然第二个性质存在位运算,那么我们不妨将 m 二进制拆分开来先。
我们可以发现第二个性质可以表述为:假设我们将 m 拆分成多个 2 的幂次,那么我们的目标就是选择其中任意数量的 2 的幂次最终加和等于 s 。
那么这道题是不是可以转变成,我们有 k 个种类的物品,它们的价值分别为 w[i] (1<=i<=k),我们每次可以选择多个种类的物品每个拿一个,最终价值和等于 s,求最小的拿取次数 。
然后我们还可以发现:由于每次一个种类的物品只能拿一个,所以为了让我们的次数最小,我们需要让最终每个物品的个数是尽可能相等的。
这时,我们可以想到:使用二分去枚举所有物品个数的最大值,然后进行判断,尽可能缩小这个值。最后的值就是我们要找的答案 n 。
正解代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T;
inline bool check(int s, int m, int maxx){
for(int i=61;i>=0;i–){
if(m>>i & 1){
int tmp = (1ll<<i);
int t = min(maxx, s/tmp);
s -= t*tmp;
}
}
return s == 0;
}
inline void solve(){
int s,m;
cin>>s>>m;
int l = 0 , r = 1e18;
int ans = -1;
while(l<=r){
int mid = l+r>>1;
if(check(s,m,mid)){
ans = mid;
r = mid-1;
}
else l = mid+1;
}
cout<<ans<<'\\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>T;
while(T–) solve();
return 0;
}

![P11246 [GESP202409 六级] 小杨和整数拆分-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108100631-6af049a75855c-220x150.png)

