Educational Codeforces Round 187 (Rated for Div. 2)-CF-Edu-187-C. Test Generator（从低位到高位贪心考虑） · znzryb
## 题目大意
**题目描述**
给定两个整数 $s$ 和 $m$。
你需要构造一个由非负整数组成的数组 $a=[a_1, a_2, \dots, a_n]$，满足以下两个条件：
1. 数组所有元素的和等于 $s$，即 $\sum_{i=1}^n a_i = s$；
1. 对于数组中的每一个元素 $a_i$，都满足 $a_i \ \& \ m = a_i$（其中 $\&$ 表示按位与运算符）。换句话说，在每个数字 $a_i$ 的二进制表示中，只有当 $m$ 在相应位置上的二进制位也是 $1$ 时，$a_i$ 在该位置上的二进制位才可以是 $1$。
判断是否至少存在一个满足条件的数组。如果存在，求出该数组的最小可能长度 $n$；如果不存在，则输出 $-1$。
**输入格式**
第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。
每个测试用例包含一行，包含两个整数 $s$ 和 $m$（$1 \le s, m \le 10^{18}$）。
**输出格式**
对于每个测试用例，输出一个整数：
如果不存在这样的数组，输出 $-1$；
否则，输出满足条件的数组的最小可能长度 $n$。
**样例输入**
```
6
13 5
13 3
13 6
1000000007 2776648
99999999999 1
998244353 1557287
```
**样例输出**
```
3
5
-1
-1
99999999999
642
```
**样例解释**
对于部分测试用例的分析如下：
当 $s=13, m=5$ 时，答案为 $3$，因为存在一个满足条件的数组 $a=[5, 4, 4]$；
当 $s=13, m=3$ 时，答案为 $5$，因为存在一个满足条件的数组 $a=[3, 3, 3, 3, 1]$；
当 $s=13, m=6$ 时，答案为 $-1$，因为不存在满足条件的数组。
## 思路讲解
::: AI 的提示
## **核心思路**
每个 $a_i$ 都是 $m$ 的子掩码（submask），即 $a_i$ 只在 $m$ 的某些位上取 1。如果用 $n$ 个这样的数去凑总和 $s$，那么对于 $m$ 的每个 set bit 位置 $b$，我们最多可以有 $n$ 个元素在该位取 1，贡献 $n \cdot 2^b$。
**关键性质：答案关于** $n$ **单调。** $n$ 越大，每个 bit 的"容量"越大，越容易凑出 $s$。所以可以二分 $n$。
## **无解判断**
所有 $a_i$ 的最低有效位至少是 $m$ 的 lowbit（即 m & -m），所以和 $s$ 必须是 $m$ 的 lowbit 的倍数。如果不是，直接输出 $-1$。
你的 (S^M)&1 只检查了最低位奇偶性，但遗漏了更高的情况，比如 $s=6, m=4$（lowbit 是 4，$6 \% 4 \neq 0$，应该是 $-1$，但你的判断会放过它）。
## **Check 函数（贪心验证）**
给定 $n$，从高位到低位贪心：对 $m$ 的每个 set bit 位置 $b$，尽可能多用这一位，即取 $c = \min(n, \lfloor s / 2^b \rfloor)$，然后 $s \leftarrow s - c \cdot 2^b$。最后看 $s$ 是否归零。
这个贪心是正确的，因为高位是低位的倍数，多用高位只会让剩余更小，而剩余的"可整除性"不变（差值是 $2^b$ 的倍数，一定被更低位整除）。
:::
说白了就是从高位到低位贪心，因为高位你也没办法减的更多了，高位只能影响更高位，而更高位之前已经尽力解决了。因此没有后效性。
```cpp
auto check=[&](ll num_a) -> bool {
ll opS=S;
for (ll i=62;i>=0;--i) {
if ((M>>i)&1) {
ll cnt=opS/(1ll<<i);
opS-=min(cnt,num_a)*(1ll<<i);
}
}
if (opS==0) {
return true;
}
return false;
};
```
## AC代码
AC
[https://codeforces.com/contest/2203/submission/364386484](https://codeforces.com/contest/2203/submission/364386484)
::: 源代码
```cpp
/**
* Problem: C. Test Generator
* Contest: Educational Codeforces Round 187 (Rated for Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2203/problem/C
* Created: 2026-02-25 22:47:21
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
void Solve() {
ll S,M;
cin >> S >> M;
if (S%M==0) {
cout<<S/M<<"\n";
return;
}
// if ((S^M)&1) {
// cout<<-1<<"\n";
// return;
// }
auto check=[&](ll num_a) -> bool {
ll opS=S;
for (ll i=62;i>=0;--i) {
if ((M>>i)&1) {
ll cnt=opS/(1ll<<i);
opS-=min(cnt,num_a)*(1ll<<i);
}
}
if (opS==0) {
return true;
}
return false;
};
ll l=S/M,r=S;
while (l<r) {
ll mid=l+r>>1;
if (check(mid)) {
r=mid;
}else {
l=mid+1;
}
}
if (!check(l)) {
cout<<"-1\n";
return;
}
cout<<l<<"\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
*/
```
:::
## 心路历程（WA，TLE，MLE……）