Educational Codeforces Round 187 (Rated for Div. 2)-CF-Edu-187-C. Test Generator（从低位到高位贪心考虑）

题目大意

题目描述
给定两个整数 $s$ 和 $m$。
你需要构造一个由非负整数组成的数组 $a=[a_1, a_2, \dots, a_n]$，满足以下两个条件：

1. 数组所有元素的和等于 $s$，即 $\sum_{i=1}^n a_i = s$；

2. 对于数组中的每一个元素 $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$ 的倍数，一定被更低位整除）。

说白了就是从高位到低位贪心，因为高位你也没办法减的更多了，高位只能影响更高位，而更高位之前已经尽力解决了。因此没有后效性。

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

源代码

/**
 * 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……）