题目描述

给定一个包含 K个不同质数的集合 S={p1,p2,…,pK}。

如果一个数的质因子全部属于集合 S，那么我们就称这个数为谦虚数字。

例如，p1、p1p2、p1p1、p1p2p3....这些数字都是谦虚数字。

现在给定整数 K和集合 S，请你求出从小到大第 N个谦虚数字是多少。

注意，我们规定 1不是谦虚数字。

输入格式

第一行包含两个整数 K和 N。

第二行包含 K个质数。

输出格式

输出一个整数，表示第 N大的谦虚数字。

数据保证，答案在 int 范围内

数据范围

1≤K≤100，
1≤N≤10^5

样例

输入样例
4 19
2 3 5 7

输出样例
27

算法1

多路归并

思路

本题可以发现和丑数是很像的 https://www.acwing.com/file_system/file/content/whole/index/content/3607/ 丑数是给定了质因子的个数而这道题是没给定，所以我们也可以像丑数一样进行多路归并。我们不难发现，谦虚数字是用1乘以每个质因数得到的，所以我们只需要找到1乘以质因数后最小的谦逊数将他加入数组中最后找到第N个数即可。

具体步骤

将质因数存入一个数组，用vector存储谦逊的数字其中初始的vector中只有一个1，定义一个指针数组其中该指针指向的位置是质因数应该乘以的数，数组的下标是质因数。每次找到乘以质因数的谦逊数字之后找到最小的那个加入到vector中，最后判断这个谦逊数字可以由哪些质因数乘以当前指针位置得到，如果可以让指针向后++。

C++ 代码

#include<iostream>
#include<vector>

using namespace std;

const int N = 100010;
int  cnt[N], a[N]; //cnt[i]存储的是质因数为i的指针所指向的第几个数,s是存储的质因数
vector<int> q(1,1);

int main(){
    int n, k;
    cin >> n >> k;
    for(int i = 0;i < k;i++) cin >> a[i]; //存储质因数

    while(k--){
        int t = q[cnt[0]] * a[0]; //找到数列中第一个谦虚的数字
        for(int i = 1;i < n;i++) t = min(t, q[cnt[i]] * a[i]); //找到最小的
        q.push_back(t);
        for(int i = 0;i < n;i++)
            if(t == q[cnt[i]] * a[i]) cnt[i]++; //把同时满足的指针向后移动，比如质因数是2和3，6可以是2*2也可以是2*3所以都向后移动
    }
    cout << q.back();
    return 0;
}