P2723 [USACO3.1] 丑数 Humble Numbers

核心思路：多路归并 (Multi-pointer)

本题本质上是寻找第 \(N\) 小的数，且该数必须由集合 \(S\) 中的质数相乘得到。

也就是经典的丑数问题的通用版。

1. 状态定义：

   用数组 ugly[i] 存储第 \(i\) 个丑数。为了方便生成，我们设 ugly[0] = 1（作为基准种子）。

2. 指针维护：

   对于集合中的每一个质数 \(p_j\)，维护一个指针 ptr[j]。

   ptr[j] 的含义是：质数 \(p_j\) 下一步应该乘上 ugly 数组中的哪个数，才可能成为当前最小的新丑数。

3. 状态转移：

   第 \(i\) 个丑数一定是所有候选者中的最小值：

   \[ugly[i] = \min_{0 \le j < k} (ugly[ptr[j]] \times p[j]) \]

4. 去重与推进：

   选出最小值 min_val 后，所有计算结果等于 min_val 的质数指针都要 +1。

   （例如：\(2 \times 3 = 6\)，\(3 \times 2 = 6\)，此时 \(2\) 和 \(3\) 对应的指针都要前移，从而自动去重）。

复杂度分析

• 时间复杂度：\(O(N \times K)\)。我们需要循环 \(N\) 次找答案，每次遍历 \(K\) 个质数。对于 \(10^5 \times 100\) 的数据量，计算量约 \(10^7\)，在 1s 时限内非常稳。
• 空间复杂度：\(O(N + K)\)。

---

AC 代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 100005; // N 最大 100,000
const int MAXK = 105;    // K 最大 100

long long ugly[MAXN]; // 丑数数组
int p[MAXK];          // 质数集合
int ptr[MAXK];        // 对应每个质数的指针（索引）

int main() {
    // 1. 快速 I/O
    ios::sync_with_stdio(false);
    cin.tie(0);

    int k, n;
    cin >> k >> n;

    for (int i = 0; i < k; i++) {
        cin >> p[i];
        ptr[i] = 0; // 初始所有指针指向 ugly[0]
    }

    ugly[0] = 1; // 初始化基准，便于生成后续数

    // 2. 循环生成第 1 到第 n 个丑数
    for (int i = 1; i <= n; i++) {
        long long min_val = 1e18; // 设置一个足够大的初始值

        // 第一步：找出当前能生成的最小值
        for (int j = 0; j < k; j++) {
            long long val = ugly[ptr[j]] * p[j];
            if (val < min_val) {
                min_val = val;
            }
        }

        ugly[i] = min_val;

        // 第二步：推进所有生成了该最小值的指针 (关键去重步骤)
        for (int j = 0; j < k; j++) {
            if (ugly[ptr[j]] * p[j] == min_val) {
                ptr[j]++;
            }
        }
    }

    cout << ugly[n];
    return 0;
}