题目理解

我们需要找到第 $K$ 大的 $N$-伪光滑数。$N$-伪光滑数的定义是：

1. 大于 $1$ 的整数 $M$
2. 质因数分解有 $k$ 项（可重复）
3. 最大质因子 $a_k < 128$
4. 满足 ${a_k}^k \leq N$

换句话说，$M$ 只能由小于 $128$ 的质数构成，且最大质因子的指数 $k$ 满足 ${a_k}^k \leq N$。

---

关键分析

1. 质数范围

由于最大质因子 $a_k < 128$，我们只需要考虑小于 $128$ 的质数。小于 $128$ 的质数有： $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127$ 共 $31$ 个质数。

2. 数的结构

每个 $N$-伪光滑数可以表示为： [ M = p_1^{e_1} p_2^{e_2} \cdots p_m^{e_m} ] 其中：

• $p_1 \leq p_2 \leq \cdots \leq p_m < 128$
• $p_m$ 是最大质因子
• 设 $k = e_1 + e_2 + \cdots + e_m$（总因子数）
• 满足 $p_m^k \leq N$

3. 问题转化

我们需要生成所有满足条件的 $M$，然后找出第 $K$ 大的。

---

暴力方法的困难

直接枚举所有可能的指数组合：

• 质数数量：$31$ 个
• 每个质数的指数可能很大（因为 $N$ 可达 $10^{18}$）
• 组合数量巨大，无法直接枚举

---

堆（优先队列）方法

我们可以使用最大堆来维护当前最大的 $N$-伪光滑数：

算法步骤：

1. 初始化：将所有单个质数 $p$（满足 $p \leq N$ 且 $p < 128$）加入最大堆
2. 循环 K 次：
   • 弹出堆顶（当前最大值）
   • 生成所有可能的"子节点"加入堆中
3. 第 K 次弹出的就是答案

关键：如何生成子节点？

如果当前数为 $M = p_1^{e_1} p_2^{e_2} \cdots p_m^{e_m}$，其中 $p_1 \leq p_2 \leq \cdots \leq p_m$，那么子节点可以是：

• 用 $p_m$ 替换为下一个更大的质数（如果存在）
• 在 $M$ 上乘以 $p_m$（保持最大质因子不变）

但需要确保仍然满足 $p_m^k \leq N$。

---

更高效的方法：按最大质因子分类

我们可以按最大质因子 $p$ 分类处理：

对于每个最大质因子 $p$：

• 总因子数 $k$ 满足 $p^k \leq N$，所以 $k \leq \lfloor \log_p N \rfloor$
• 用小于等于 $p$ 的质数构造所有可能的数
• 使用动态规划或DFS生成

然后合并所有类，找出第 $K$ 大的数。

---

具体实现方案

步骤1：预处理质数

生成所有小于 $128$ 的质数。

步骤2：对每个最大质因子 $p$

使用DFS生成所有满足条件的数：

• 当前乘积 $curr$
• 可用质数列表（小于等于 $p$）
• 已用因子数 $cnt$
• 约束：$curr \times p \leq N$ 且 $p^{cnt+1} \leq N$

步骤3：收集所有数并排序

由于 $K \leq 800000$，我们只需要保留最大的 $K$ 个数。

---

使用堆维护前K大

我们不需要生成所有数，只需要维护一个大小为 $K$ 的小根堆：

1. 初始化空堆
2. 对于每个最大质因子 $p$：
   • 使用DFS生成数，当堆大小达到 $K$ 时：
     • 如果新数大于堆顶，替换堆顶
     • 否则剪枝
3. 最终堆顶就是第 $K$ 大的数

---

DFS生成优化

在DFS时，我们可以：

• 按质数从大到小尝试（优先产生大数）
• 及时剪枝：如果当前数乘以剩余最大可能值仍然小于堆顶，则剪枝

---

进一步优化

1. 避免重复计算

使用记忆化或更好的状态表示避免重复生成相同的数。

2. 更智能的剪枝

在DFS时，如果当前路径不可能产生比堆顶更大的数，及时剪枝。

3. 分批处理

对于不同的最大质因子，可以并行处理。

---

复杂度分析

• 质数数量：$31$ 个
• 每个质数的DFS分支：由于 $N \leq 10^{18}$，深度最多约 $60$
• 总状态数：可接受的范围
• 堆操作：$O(K \log K)$

---

样例验证

输入：

12345 20

处理过程：

• 生成所有满足条件的 $12345$-伪光滑数
• 找出第 $20$ 大的数
• 输出：9167

验证：$9167$ 确实是一个 $12345$-伪光滑数 ✓

---

总结

本题的关键在于：

1. 理解 $N$-伪光滑数的定义和约束条件
2. 使用按最大质因子分类的方法减少搜索空间
3. 使用堆维护前 $K$ 大的数，避免生成所有数
4. 在DFS时进行有效的剪枝优化

这是一个典型的组合数学+搜索优化问题，考察了对数论性质和算法优化的理解。