---
title: "谦虚数字"
created: 2025-11-28
tags:
  - 算法
---

# 谦虚数字

## 题目 [谦虚数字](https://www.acwing.com/problem/content/1380/)

![[image-1c1d7c27.png]]

## 思路分析

与超级丑数变化的地方在于 1不是第一个丑数了

但其他数还是得从1变化而来

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

struct Data{

    int v,p,k;//当前值 质数 索引

    bool operator<(const Data& other)const{

        return v>other.v;

    }

};

int n,k;

int main()

{

    cin>>k>>n;

    n++;//1不是谦虚数字仅用于生成其他谦虚数字

    vector<int> uglynums(1,1);//存储谦虚序列初始值1

    priority_queue<Data> heap;//下一个可能的谦虚数字

    while(k--){

        int p;cin>>p;

        heap.push({p, p, 0});

    }

    while(uglynums.size()<n){

        auto minval = heap.top().v;

        uglynums.push_back(minval);//这个数字加入谦虚数字序列

        //弹出所有重复minVal 移动指针（添加新数）

        while (!heap.empty() && heap.top().v == minval){

            auto ugly=heap.top();

            heap.pop();

            heap.push({ugly.p * uglynums[ugly.k + 1], ugly.p, ugly.k + 1});

        }

    }

    cout<<uglynums.back();

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/多路归并相关问题/蚯蚓|蚯蚓]] 🏠 [[00-刷题理模型]] ➡️ [[超级丑数|超级丑数]]