【例2-2】Blah数集

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

用两个指针分别加工升序序列已生成前缀的 2x+1 与 3x+1 两族候选，队首取小接回序列、相等双消费去重，O(n) 得到第 n 个 Blah 数，多组询问逐组计算。

OJ: roj

题目 ID: 1333

难度:普及-

标签:贪心多路归并双指针python

创建: 2026-09-30 05:44

更新: 2026-10-07 13:50

前置题目
shumeng CSP201809B买菜B 的多路归并直接复用 A 教的「比较当前两段后推进结束更早一方」这一具体双指针推进规则：A 是 end 更早的区间不可能再相交故前移其指针（main.cpp:40-44），B 是两族队首取小者、被消费的族指针前移一格（main.py:20-21），只把「结束时刻比较」换成「候选值比较」、并在相等时叠加双消费去重与堆模拟对照，属 A→B 的台阶。shumeng CSP202006B稀疏向量A 教的「两条有序序列各自用只进不退的指针，比较当前队首再决定谁前移、相等则双方同时处理」正是 B 的 2x+1 与 3x+1 两族队首归并取小、相等双消费去重所用的同一步骤；B 只是把它从两个已给的有序稀疏表搬到两条自产流水线上，并叠加了 A 未教的「父小于子 ⇒ 已生成前缀可回喂、生成到第 n 项」这一自产自销机制，故属真实复用且台阶合理。

目录

  1. 题目描述
  2. 思路
  3. 参考代码

题目描述

大数学家高斯小时候发现一种有趣的自然数集合 Blah：以 a 为基的集合 Ba 定义为——a 是 Ba 的第一个元素；如果 x 在 Ba 中，则 2x+1 和 3x+1 也都在 Ba 中；没有其他元素。将 Ba 中元素按升序排列，问第 N 个元素是多少。

输入很多行，每行两个数字：基 a（1≤a≤50）与序号 n（1≤n≤1000000）。对每组输入，输出 Ba 的第 n 个元素值。

输入样例：

text
1 100
28 5437

输出样例：

text
418
900585

思路

把升序序列记作 q，q 中每个元素（除 a 外）都由某个更小的元素经 2x+1 或 3x+1 生成，所以用两个指针分别指向 q 中"待加工"的位置，2q_p+1 与 3q_r+1 各自构成递增候选。每轮取两族队首的较小者接到 q 尾部并把对应指针后移，两族候选相等时两个指针同时后移（天然去重），生成满 n 个数即为答案，每组询问 O(n)。

参考代码

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-09-28 16:40
# update_at: 2026-09-28 16:40

import sys


def blah(a: int, n: int) -> int:
    """求以 a 为基的 Blah 数集升序排列后的第 n 个元素。"""
    seq = [0] + [a]  # q[1] = a；留出下标 0 的哨兵位，双指针都从 1 出发
    head2, head3 = 1, 1  # 2x+1 家族 / 3x+1 家族各自消费到的前缀位置
    for _ in range(n - 1):  # 已有第 1 个元素，再生成 n-1 个
        x = seq[head2] * 2 + 1
        y = seq[head3] * 3 + 1
        smaller = x if x < y else y  # 两族队首的较小者就是下一个数
        seq.append(smaller)
        head2 += x <= y  # x 被消费（含相等时两族同时消费）
        head3 += y <= x
    return seq[n]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    out: list[str] = []
    for a in data:  # 读到文件尾为止，每组两个数：基 a 与序号 n
        n = next(data)
        out.append(str(blah(a, n)))
    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-05 10:11
 * update_at: 2026-10-05 10:11
 */

#include <cstdio>

typedef long long ll;

const int MAXN = 1000005;

ll q[MAXN]; // q[i] 表示 Blah 数集升序排列的第 i 个元素

int main() {
    ll a, n;
    while (scanf("%lld %lld", &a, &n) == 2) {
        q[1] = a;
        int p = 1; // 2x+1 一族的队首指针
        int r = 1; // 3x+1 一族的队首指针
        for (int i = 2; i <= n; ++i) {
            ll x = 2 * q[p] + 1; // 2x+1 一族的队首候选
            ll y = 3 * q[r] + 1; // 3x+1 一族的队首候选
            if (x < y) {
                q[i] = x;
                p = p + 1;
            } else if (y < x) {
                q[i] = y;
                r = r + 1;
            } else { // 两族候选相等时同时消费，天然去重
                q[i] = x;
                p = p + 1;
                r = r + 1;
            }
        }
        printf("%lld\n", q[n]);
    }
    return 0;
}