形式化题目

给定素数集合 $S=\{p_1,p_2,\dots,p_K\}$。称正整数 $x$ 是丑数，当且仅当 $x$ 的所有质因数都取自 $S$，即存在 $e_1,\dots,e_K\geqslant 0$ 使

（$\sum e_i\geqslant 1$ 的意思正是 $x\neq 1$：1 不算丑数。）

求所有丑数从小到大排成的序列中第 $N$ 个数。

样例 4 19 / 2 3 5 7 的丑数序列开头是

第 19 项是 $27$。

正解

思路

先看直接枚举为什么行不通。 最直接的想法是从 $x=2$ 往上逐个判断：把 $x$ 反复除以 $S$ 中的素数，能除到 1 就是丑数，数满 $N$ 个就输出。判断单个数只要 $O(K\log x)$，但第 $N$ 个丑数最大可以是 $2^{100000}$（$K=1$ 时），值域完全不可枚举。瓶颈是"沿着数轴盲目扫描"，而不是"沿着丑数序列前进"。

所以要把目标改成：按从小到大的顺序，一个一个地把丑数"造"出来，而不是去找。

关键观察：每个素数自带一条单调递增的候选队列。 固定 $p_j\in S$。任何丑数必然能写成 $a\cdot p_j$ 的形式，其中 $a$ 或者等于 1，或者是一个更小的丑数。把已经造出来的丑数序列记为

其中 $a_0=1$ 只是为了当乘数的起点，本身不算丑数。那么 $p_j$ 能贡献的候选值恰好是

因为 $a$ 严格递增、$p_j\geqslant 2$，这个序列也严格递增。于是每个素数 $p_j$ 等价于一条有序的"生产者队列"，它现在能给出的最小候选就是 $a_{\mathrm{idx}_j}\cdot p_j$，其中 $\mathrm{idx}_j$ 是它已经用掉了几个乘数。

反过来说：任何丑数都能写成某个 $a_x p_j$（取它的任意一个素因子即可），而任何 $a_xp_j$ 都是丑数。所以

必须处理打平。 同一个值可能有多种拆分方式：样例里 $a_1p_2=a_2p_1=6$（即 $2\times3=3\times2$）、$a_1p_3=a_4p_1=10$（$2\times5=5\times2$）、$a_1p_4=a_6p_1=14$（$2\times7=7\times2$），这些值会同时出现在两条队列的队首。如果只推进其中一条，下一轮还会再取到同一个值，序列里出现重复项，$N$ 的计数就全错了。正确做法是把所有等于当前最小值的生产者一起推进一格——它们已经把这个值交付过了，谁都不该再交付第二次。

从 $O(NK)$ 到 $O(N\log K)$。 既然每次只做"取 $K$ 个候选的最小值"，就可以把 $K$ 个生产者放进小根堆，堆元素写成 (候选值, 素数下标)：

1. 堆顶就是全局最小候选值 $cur$，也就是下一个丑数，$O(1)$ 读出；
2. 把 $cur$ 追加进 $a$；
3. 循环弹出所有堆顶等于 $cur$ 的元素，把对应素数的下标 $+1$，再把新候选 $a_{\mathrm{idx}_j}p_j$ 推回堆——这一轮的打平者被一次性消费干净；
4. 重复 $N$ 轮，输出 $a_N$。

天真的实现里，"取最小"要扫 $K$ 个候选，单轮 $O(K)$，整个算法 $O(NK)$；堆把单轮取最小降到 $O(\log K)$。堆的规模始终是 $K$，这是 $O(\log K)$ 的来源。实际打平比例远小于上界：$K=8$ 的 humble5 弹出 456706 次（$4.57N$），$K=100$ 的 humble11 只有 346678 次（$3.47N$）。在 $K=100,N=10^5$ 这组上，扫描写法约 0.54 s，堆写法约 0.11 s。

下面这段表格把样例的前 12 轮摊开。列是每个素数当前给出的候选值，加粗的是本轮的最小值，最后一列是这一轮被一起推进的素数。

观察重点有两处。第一，每一列都是单调递增的，这正是"生产者队列"的性质，也是下标只增不减的依据。第二，第 5、9、10、11、12 轮的加粗格子都不止一个：第 5 轮 $6$ 同时来自 $p_1=2$（$a_2\cdot2$）与 $p_2=3$（$a_1\cdot3$），第 9 轮 $10$ 同时来自 $p_1=2$（$a_4\cdot2$）与 $p_3=5$（$a_1\cdot5$），第 10 轮 $12$ 同时来自 $p_1=2$（$a_5\cdot2$）与 $p_2=3$（$a_3\cdot3$），这些就是必须一起推进的情形。若第 5 轮只推进 $p_1=2$，第 6 轮的候选里仍会有 $6$，答案会错。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39#!/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-01 04:42
# update_at: 2026-10-01 04:47

import sys
from heapq import heapify, heappop, heappush


def nth_humble(primes: list[int], n: int) -> int:
    """返回质因数全部取自 primes 的正整数中第 n 小的那个（1 不算丑数）。"""
    # 每个素数 p_j 只管一条候选队列 a[0]*p_j, a[1]*p_j, ...；idx[j] 是它已用掉的乘数个数。
    idx = [0] * len(primes)
    a = [1]                                              # a[0]=1 只是乘数起点，本身不是丑数
    heap = [(p, j) for j, p in enumerate(primes)]        # 堆元素带 j，弹出后才知道该推进哪个素数
    heapify(heap)

    for _ in range(n):
        cur = heap[0][0]                                 # 堆顶是所有队列的最小候选 = 下一个丑数
        a.append(cur)
        while heap[0][0] == cur:                         # 打平的队列一起推进，否则下一轮会重复产出 cur
            _value, j = heappop(heap)
            idx[j] += 1
            heappush(heap, (a[idx[j]] * primes[j], j))   # 新候选引用刚生成的 cur，因而严格大于 cur

    return a[n]                                          # a[0] 是哨兵，第 n 个丑数正是 a[n]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    k, n = next(data), next(data)
    primes = [next(data) for _ in range(k)]
    print(nth_humble(primes, n))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77/**
 * 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-06 09:33
 * update_at: 2026-10-06 09:33
 */

// 丑数：质因数全部取自给定素数集合 S 的正整数（1 不算）。
// 多路归并：每个素数 p_j 对应一条候选队列 a[0]*p_j, a[1]*p_j, ...（a[0]=1 只是起点），
// 队列单调递增，用下标 idx[j] 表示已用掉几个乘数；下一个丑数是 K 个队首的最小值。
// 用小根堆取最小，O(N log K)。

#include <cstdio>
#include <queue>
#include <vector>

typedef long long ll;

const int MAXK = 105;
const int MAXN = 100005;

int k, n;
int p[MAXK];    // p[j]：素数集合 S 的第 j 个素数（下标从 0 开始）
ll idx[MAXK];   // idx[j]：素数 p_j 已经用掉的乘数个数，当前候选是 a[idx[j]] * p[j]
ll a[MAXN];     // a[0]=1 只是乘数起点不算丑数，a[i] 是从小到大第 i 个丑数

// 堆元素 (候选值, 素数下标)：小根堆按候选值比较，弹出后才知道该推进哪个素数
struct Cand {
    ll v;
    int j;
};

// 堆的比较器：候选值小的先出堆
struct CandCmp {
    bool operator()(const Cand &x, const Cand &y) const {
        return x.v > y.v;
    }
};

std::priority_queue<Cand, std::vector<Cand>, CandCmp> heap;

// 多路归并：循环 n 轮，每轮取堆顶最小候选作为下一个丑数，
// 打平（多个队列同时给出最小值）的队列一起推进，避免重复产出
ll solve() {
    a[0] = 1; // 乘数起点哨兵，本身不算丑数
    for (int j = 0; j < k; j++) {
        idx[j] = 0;
        Cand c;
        c.v = p[j];
        c.j = j;
        heap.push(c); // 每条队列的初始候选 a[0] * p[j] = p[j]
    }

    for (int i = 1; i <= n; i++) {
        ll cur = heap.top().v; // 所有队首的最小值就是下一个丑数
        a[i] = cur;
        // 把所有等于 cur 的队首都推进一格：它们已经交付过 cur，不许再交付第二次
        while (heap.top().v == cur) {
            int j = heap.top().j;
            heap.pop();
            idx[j]++;
            Cand c;
            c.v = a[idx[j]] * p[j]; // 新候选引用刚生成的 cur，因而严格大于 cur
            c.j = j;
            heap.push(c);
        }
    }
    return a[n];
}

int main() {
    scanf("%d %d", &k, &n);
    for (int j = 0; j < k; j++) scanf("%d", &p[j]);
    printf("%lld\n", solve());
    return 0;
}

复杂度

• 时间复杂度：$O(N\log K)$。
  • 堆的规模始终是 $K$，所以每次堆操作 $O(\log K)$；$K\leqslant 100$ 时 $\log K\leqslant 7$。
  • 总操作次数是 $O(N)$：被弹出的候选值 $a_{\mathrm{idx}_j}p_j$ 就是某个已产出的丑数 $a_t\ (t\leqslant N)$，而 $a_t$ 每含一个属于 $S$ 的素因子 $p_j$ 就会被弹出一次（此时 $a_t/p_j$ 也是丑数，早已在序列里）。题目保证答案在 signed 32-bit 内，即 $a_t<2^{31}$，所以每个 $a_t$ 至多 30 个素因子，总弹出次数不超过 $30N$，推入次数与它相等。
  • 实测打平比例远小于上界：$K=8$ 的 humble5 弹出 456706 次（$4.57N$），$K=100$ 的 humble11 只有 346678 次（$3.47N$）。
• 空间复杂度：$O(N+K)$。丑数数组存 $N+1$ 个数，堆存 $K$ 个元素，下标数组 $K$ 个。

总结

这道题的核心是把"枚举值域"换成"沿着序列生成"：每个素数 $p_j$ 对应一条单调队列 $a_0p_j,a_1p_j,a_2p_j,\dots$，用一个下标 $\mathrm{idx}_j$ 就能代表整条队列；下一个丑数永远是 $K$ 个队首的最小值，取完之后把取到最小值的那些队列一起推进一格。

两个容易写错的地方：一是打平必须一起推进（while heap[0][0] == cur 而不是 if），否则 $6=2\times3=3\times2$ 这类数会被生成两次；二是先 append 再推进下标，这样新候选值才能引用到刚生成的丑数，同时保证它严格大于刚取出的值，不会死循环。用堆替代线性扫，把每轮取最小从 $O(K)$ 降到 $O(\log K)$，最坏一组真实数据从约 0.54 s 降到 0.11 s。

12 组真实测试数据全部通过，最慢一组 0.125 s、峰值内存 18.6 MB，相对 1000 ms / 128 MB 的限制余量充足。

图示解析

这张图串起本题从建模到得到答案的主线：

1
2
3
4
5
6
7素数集合 S
`- 观察：p_j 的候选是 a[0]*p_j, a[1]*p_j, a[2]*p_j ...  单调递增
   `- 每条队列只需一个下标 idx_j
      `- 下一个丑数 = min_j a[idx_j] * p_j
         |- 若有多个队列同时等于最小值
         |  `- 把它们一起推进，避免同一个值产出两次
         `- 用下标推进 K 次 -> 取第 N 个

先看"每个素数对应一条单调队列"这一步：它把"枚举所有 $S$-光滑数"换成"只比较 $K$ 个队首"。再顺着分支检查打平处理：不一起推进就会生成重复项，$N$ 的计数随之失效。最后一行说明循环只做 $N$ 轮，每轮推进若干个下标，序列天然有序，$a_N$ 就是答案。