思路与算法

令f(n)计(n,2n]中恰k个1的数，直接比较相邻区间可得f(n+1)-f(n)=[popcount(n)=k-1]，且f(0)=0。因此f(n)等于[0,n)中恰k-1个1的数。预处理64位组合数，用逐位计数求f；二分第一次f≥m与第一次f≥m+1，两界之间就是全部解。k=1时所有正n都有f=1，单独输出无限。

正确性说明

相邻区间新增2n+1、2n+2并删去n+1，后两者popcount相同抵消，只剩popcount(n)+1=k的指示项，故恒等式成立。前缀计数单调，两个下界刻画完整同值平台；平台长度即有限解数。题目保证10^18以内存在解，所需下一组合跳点在本题64位范围内，参考程序可输出任一平台元素。

复杂度

组合表初始化O(64²)，每组两次64步二分，每次计数O(64)，总O(64²+t·64²)时间，O(64²)空间。

易错点

n必须正，m=0平台从1开始。k=64,m=0时解数可达2^63-1，使用无符号64位，二分用l+(r-l)/2。多解特判会验证实际n的计数及全部解数，不要求参考程序选同一个n。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using U = unsigned long long;
U C[66][66];
U countLess(U n, int k) {
    U s = 0;
    for (int b = 63; b >= 0; b--)
        if (n >> b & 1) {
            if (k >= 0 && k <= b)
                s += C[b][k];
            if (--k < 0)
                break;
        }
    return s;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i = 0; i <= 64; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++)
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
    int T;
    cin >> T;
    while (T--) {
        U m;
        int k;
        cin >> m >> k;
        if (k == 1) {
            if (m == 0)
                cout << "0 0\n";
            else
                cout << "1 -1\n";
            continue;
        }
        auto lower = [&](U wanted) {
            U l = 1, r = ULLONG_MAX;
            while (l < r) {
                U mid = l + (r - l) / 2;
                if (countLess(mid, k - 1) >= wanted)
                    r = mid;
                else
                    l = mid + 1;
            }
            return l;
        };
        U l = m ? lower(m) : 1, r = lower(m + 1);
        cout << l << ' ' << r - l << '\n';
    }
}