寻找整数

GitHub跳转原题关系图返回列表

用 f(n)=#{j<n: popcount(j)=k-1} 把合法 n 压成一段连续区间,位贪心求第 m 个候选数,O(log n) 得最小 n 与解的个数。

OJ: roj

题目 ID: 1777

难度:提高

标签:位运算组合数学贪心python

创建: 2026-10-08 01:55

更新: 2026-10-08 01:55

形式化题目

给定 m,km, k,求正整数 nn,使得区间 (n,2n](n, 2n] 中的整数恰好有 mm 个在二进制下含有 kk 个 11。 多组询问,每组输出任意一个满足条件的 nn(要求 n⩽264−1n \leqslant 2^{64}-1), 以及满足条件的 nn 的总个数(无穷多时输出 −1-1)。

记 popcount(x)\mathrm{popcount}(x) 为 xx 的二进制中 11 的个数,并定义

f(n)  =  #{ x:n<x⩽2n, popcount(x)=k }. f(n) \;=\; \#\{\,x : n < x \leqslant 2n,\ \mathrm{popcount}(x) = k\,\}.

那么每组询问就是一个方程:

求 n⩾1 使 f(n)=m,并给出解的个数(0⩽m⩽1018, 1⩽k⩽64). \text{求 } n \geqslant 1 \text{ 使 } f(n) = m, \qquad \text{并给出解的个数(} 0 \leqslant m \leqslant 10^{18},\ 1 \leqslant k \leqslant 64\text{)}.

题面保证 101810^{18} 以内存在满足条件的 nn。以样例 m=1, k=2m=1,\ k=2 为例: n=2n=2 时区间是 {3,4}\{3,4\},其中 3=1123 = 11_2 有 2 个 11、4=10024 = 100_2 有 1 个 11, 恰有 11 个符合,故输出 2 1。

数据来源说明

本题与 Codeforces 431D Random Task 同源(题面逐字对应)。 但 101810^{18} 内的测试数据由 data.py 现场生成,本仓库的 std.cpp 也出自同一次整理, 并非官方数据;额外追问的「解的个数」一项更是原题所无(原题只要求输出一个 nn)。 本文的推导独立于 std.cpp,结论已用暴力枚举在 n⩽3000n \leqslant 3000、k⩽13k \leqslant 13 范围内逐点核对。

正解

思路

朴素做法。 从 n=1n = 1 开始枚举,对每个 nn 扫一遍 (n,2n](n, 2n] 统计 popcount=k\mathrm{popcount} = k 的个数。 单次统计就要 O(n)O(n) 步,而 nn 可达 101810^{18},且 mm 所对应的 nn 还未必小 (k=31k=31 时合法 nn 已逼近 101810^{18})。枚举路线完全没有利用区间滑动时的代数结构。

关键恒等式。 把 f(n+1)−f(n)f(n+1) - f(n) 算出来。f(n)f(n) 统计 (n,2n](n, 2n],f(n+1)f(n+1) 统计 (n+1,2n+2](n+1, 2n+2], 两者做差只剩三个元素:

f(n+1)−f(n)=[popcount(2n+1)=k]+[popcount(2n+2)=k]−[popcount(n+1)=k]. f(n+1) - f(n) = [\mathrm{popcount}(2n+1)=k] + [\mathrm{popcount}(2n+2)=k] - [\mathrm{popcount}(n+1)=k].

而 2n+2=2(n+1)2n+2 = 2(n+1) 是左移一位,左移不改变 11 的个数,所以后两项恒等、直接抵消:

f(n+1)−f(n)=[popcount(2n+1)=k]=[popcount(n)=k−1].(1) f(n+1) - f(n) = [\mathrm{popcount}(2n+1) = k] = [\mathrm{popcount}(n) = k-1]. \tag{1}

(最后一步因为 2n+12n+1 就是 nn 左移一位再补个 11。)于是 ff 单调不减、每次至多涨 11, 且能直接展开前缀:

f(n)  =  ∑j=1n−1[popcount(j)=k−1]  =  #{ j:0⩽j<n, popcount(j)=k−1 }.(2) f(n) \;=\; \sum_{j=1}^{n-1} [\mathrm{popcount}(j) = k-1] \;=\; \#\{\,j : 0 \leqslant j < n,\ \mathrm{popcount}(j) = k-1\,\}. \tag{2}

这一步把「区间计数」变成了「排名」:f(n)=mf(n) = m 就是说「恰有 mm 个『含 k−1k-1 个 11』的数 严格小于 nn」。把所有 popcount=p\mathrm{popcount} = p(p=k−1p = k-1)的非负整数从小到大排成

a0<a1<a2<⋯ ,a0=1⋯1⏟p=2p−1,a_0 < a_1 < a_2 < \cdots, \qquad a_0 = \underbrace{1\cdots1}_{p} = 2^{p}-1,

则 f(n)=mf(n) = m 等价于 am−1<n⩽ama_{m-1} < n \leqslant a_m,于是解的集合是一段连续区间:

mm 合法 nn 的范围 最小 nn 解的个数
m⩾1m \geqslant 1 [ am−1+1, am ][\,a_{m-1}+1,\ a_m\,] am−1+1a_{m-1}+1 am−am−1a_m - a_{m-1}
m=0m = 0 [ 1, a0 ]=[ 1, 2p−1 ][\,1,\ a_0\,] = [\,1,\ 2^{p}-1\,] 11 2p−12^{p}-1

这也顺带解释了为什么解一定是「连续一段」而不是零散分布——因为 ff 每次只涨 00 或 11, 值 mm 只可能被一整段 nn 连续取到。

特例 k=1k = 1。 此时 p=0p = 0,而含 00 个 11 的非负整数只有 j=0j = 0 一个, 由 (2) 得 f(n)≡1f(n) \equiv 1(n⩾1n \geqslant 1)。所以 m=1m = 1 时所有正整数 nn 都合法, 个数为无穷多,输出 1 -1。

求第 rank\text{rank} 个候选数 arank−1a_{\text{rank}-1}:按位贪心。 从最高位到最低位扫描, 维护「已经放下的 11 的个数 used」。在第 ii 位,如果这一位取 00, 那么低 ii 位里还要凑出 need = p - used 个 11,方案数是组合数 (ineed)\binom{i}{\text{need}}:

  • 若 rank⩽(ineed)\text{rank} \leqslant \binom{i}{\text{need}},目标落在这支里,本位取 00;
  • 否则减去这一支的方案数,本位取 11、used 加一。

扫完 64 位得到的就是 arank−1a_{\text{rank}-1},单次 O(64)O(64)。这就是「组合数进制的第 kk 小」, 和 LeetCode 的「字典序第 kk 小数」是同一套贪心。

以样例 m=1, k=2m = 1,\ k = 2 走一遍:p=1p = 1,am−1=a0a_{m-1} = a_0 是最小的含 1 个 11 的数 (贪心从最高位看,第 0 位方案数 (01)=0<1\binom{0}{1} = 0 < 1,只能取 11,得 a0=1a_0 = 1); a1=2a_1 = 2。于是最小 n=a0+1=2n = a_0 + 1 = 2,个数 =a1−a0=1= a_1 - a_0 = 1,输出 2 1,与样例一致。

无解的处理。 题面保证 101810^{18} 内有解,但 k=64k = 64 时含 6363 个 11 的数只有 263−12^{63}-1 一个,故 m⩾1m \geqslant 1 必然无解。代码统一用 (64p)<m+1\binom{64}{p} < m+1 判断「2642^{64} 范围内凑不出第 m+1m+1 个候选」,输出 0 0 兜底。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 01:55
# update_at: 2026-10-08 01:55

import sys
from math import comb

BITS = 64  # n 的二进制位数上界:题目要求输出的 n 落在 [1, 2^64 - 1]


def kth_number(rank: int, ones: int) -> int:
    """第 rank 小(rank 从 1 起)的「二进制恰有 ones 个 1」的非负整数。"""
    x = 0
    used = 0
    for i in range(BITS - 1, -1, -1):
        # 本位取 0 时,低位 i 位里还要凑出 need 个 1,方案数为 C(i, need)
        need = ones - used
        ways = comb(i, need) if 0 <= need <= i else 0
        if rank > ways:  # 目标不在「本位取 0」这一支里,本位必须取 1
            rank -= ways
            x |= 1 << i
            used += 1
        if used == ones:
            break  # 1 已放满,低位全填 0
    return x


def answer(m: int, k: int) -> tuple[int, int]:
    """f(n) = m 时的 (最小 n, 解的个数);个数 -1 表示无穷多。

    恒等式 f(n) = #{ j < n : popcount(j) = k-1 } 把 n 的取值压成一段连续区间:
    m >= 1 时是 [a_{m-1}+1, a_m](a_i 为第 i+1 个候选),m == 0 时是 [1, 2^(k-1)-1]。
    """
    if k == 1:
        return (1, -1) if m == 1 else (0, 0)  # 候选只有 j = 0,f 恒为 1
    p = k - 1
    if m == 0:
        return 1, (1 << p) - 1
    if comb(BITS, p) < m + 1:
        return 0, 0  # 2^64 内凑不出 m+1 个候选,题面保证不会出现
    low = kth_number(m, p)      # a_{m-1}
    high = kth_number(m + 1, p)  # a_m
    return low + 1, high - low


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    t = next(data)
    out: list[str] = []

    for _ in range(t):
        m, k = next(data), next(data)
        first, count = answer(m, k)
        out.append(f"{first} {count}")

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 01:55
 * update_at: 2026-10-08 01:55
 */
// 1777《寻找整数》:给定 m, k,求正整数 n 使 (n, 2n] 中恰有 m 个数二进制含 k 个 1。
//
// 关键恒等式(本解的全部依据):
//   f(n) = #{ x : n < x <= 2n 且 popcount(x) = k }
//        = #{ j : 0 <= j <= n-1 且 popcount(j) = k-1 }。
// 推导:把 (n, 2n] 拆成偶数与奇数。偶数 x = 2y (y <= n) 的 popcount 等于 popcount(y);
//   奇数 x = 2y+1 的 popcount 等于 popcount(y)+1,且 2y+1 <= 2n 等价于 y <= n-1。
//   于是偶数部分的贡献正是 f(n) 里的「popcount(y) = k」那半边,与 #{(0,n] 中 popcount=k}
//   逐项抵消,只剩奇数部分 #{(0,n) 中 popcount = k-1},即上面的恒等式。
// 所以 f(n) = m 等价于「恰有 m 个 popcount 为 k-1 的非负整数严格小于 n」。
// 设 a_i 是第 i+1 小(下标 0 起)的「popcount = p」的整数(p = k-1),则
//   m >= 1:n 的取值恰为闭区间 [a_{m-1}+1, a_m],最小 n = a_{m-1}+1,解的个数 = a_m - a_{m-1};
//   m == 0:n 的取值恰为 [1, a_0] = [1, 2^p - 1],最小 n = 1,个数 = 2^p - 1;
//   k == 1:p = 0 时只有 j = 0 一个候选,f(n) 恒等于 1,故 m = 1 有无穷多解(个数记 -1)。
// a_i 用「按二进制位从高到低贪心」求出:本位取 0 时低位有 C(i, 剩余个数) 种填法,
// 与 rank 比较即可决定本位取 0 还是取 1,一次 O(64)。
//
// 复杂度:预处理组合数 O(64^2);每组询问 2 次 O(64) 贪心 → 单组 O(log n)。
//   t <= 2000 时总计约 2.6e5 次基本运算。空间 O(64^2)。
// 数值范围:n 至多 2^64-1,组合数最大 C(64,32) ≈ 1.83e18,全部用 unsigned long long。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull; // 答案 n 允许取到 2^64-1,超出 ll 上界,必须用无符号

const int BITS = 64; // 二进制位数上界:题目要求输出的 n 落在 [1, 2^64 - 1]
ull binom[BITS + 1][BITS + 1]; // binom[i][j] = 组合数 C(i, j),j > i 处保持 0

// 组合数表:数位贪心与无解判定都要反复查,直接按杨辉三角打表
void init_binom() {
    for (int i = 0; i <= BITS; i++) {
        binom[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j];
        }
    }
}

// 第 rank 小(rank 从 1 起)的「二进制恰有 ones 个 1」的非负整数
ull kth_number(ull rank, int ones) {
    ull x = 0;
    int used = 0;
    for (int i = BITS - 1; i >= 0; i--) {
        // 本位取 0,低位 i 位里还要凑出 need 个 1,方案数就是 C(i, need)
        int need = ones - used;
        ull ways = (need >= 0 && need <= i) ? binom[i][need] : 0ULL;
        if (rank > ways) { // 第 rank 个不在「本位取 0」这一支里
            rank -= ways;
            x |= 1ULL << i;
            used++;
        }
        if (used == ones) break; // 1 已经放满,低位全填 0
    }
    return x;
}

int main() {
    init_binom();
    int t;
    if (scanf("%d", &t) != 1) return 0;
    while (t--) {
        ull m;
        int k;
        if (scanf("%llu %d", &m, &k) != 2) break;
        if (k == 1) { // 候选只剩 j = 0,f(n) 恒为 1
            if (m == 1) printf("1 -1\n");
            else printf("0 0\n"); // 题面保证 10^18 内不会出现
            continue;
        }
        int p = k - 1; // 只需数「popcount = p 且严格小于 n」的整数个数
        if (m == 0) {
            // n 取遍 [1, 2^p - 1],最小 n 是 1,个数 2^p - 1
            printf("1 %llu\n", (1ULL << p) - 1);
            continue;
        }
        if (binom[BITS][p] < m + 1) { // 2^64 内根本凑不出 m+1 个候选,无解
            printf("0 0\n");
            continue;
        }
        ull prev_big = kth_number(m, p);     // a_{m-1}
        ull next_big = kth_number(m + 1, p); // a_m
        printf("%llu %llu\n", prev_big + 1, next_big - prev_big);
    }
    return 0;
}

复杂度

  • 时间:C++ 版预处理组合数表 O(642)O(64^2),每组询问两次按位贪心各 O(64)O(64), 故单组 O(log⁡n)O(\log n),总计 O(642+tlog⁡n)O\big(64^2 + t\log n\big);Python 版省掉建表、 每次现调 math.comb,仍是每组 O(log⁡2n)O(\log^2 n) 的量级,复杂度同阶。 t=2000t = 2000 时约 10610^6 次基本运算,实测远低于 1000 ms 限时。 注意本解法完全不依赖 mm 的大小——mm 只作为「第几名」参与组合数比较, 所以 mm 取到 101810^{18} 与取到 11 的代价完全相同。
  • 空间:组合数表 65×6565 \times 65,O(642)O(64^2),常数量级。
  • 数值范围:答案 nn 允许取到 264−12^{64}-1,超出 long long 上界, 故 C++ 里用 unsigned long long;组合数最大为 (6432)≈1.83×1018\binom{64}{32} \approx 1.83 \times 10^{18}, 同样在无符号 64 位内不溢出。Python 侧整数无上界,不需要额外处理。

总结

  • (1) 式是本题的全部内容:f(n+1)−f(n)=[popcount(2n+1)=k]f(n+1) - f(n) = [\mathrm{popcount}(2n+1)=k]。 它的证明只用了一条性质——左移一位不改变 11 的个数, 这条性质让区间的「一进一出」精确抵消掉一半,剩下的半边恰好是 nn 的排名。
  • 从「区间计数」转向「排名」:一旦看出 f(n)=#{j<n:popcount(j)=k−1}f(n) = \#\{j < n : \mathrm{popcount}(j) = k-1\}, 单调性与连续性就是显然的(ff 每次只涨 00 或 11), 解的集合也必然是一段连续区间 [am−1+1, am][a_{m-1}+1,\ a_m]。
  • 数位贪心求第 kk 小:判断「第 rank\text{rank} 个候选在哪一支」时, 低位自由位的方案数恰好是组合数 (ineed)\binom{i}{\text{need}}, 于是每个询问只需从高到低扫 64 位。这类「组合数进制」贪心 在「第 kk 小的二进制含 kk 个 11 的数」「字典序第 kk 小」等问题上可复用。
  • 特例要单独想:k=1k=1 时 ff 是常函数 11,二分或贪心都不会自然报错, 必须在入口处特判,否则「最大合法 nn」会一路跑到 2642^{64} 之外。