题目大意

给定 $k$ 个素数，求从小到大排列第 $n$ 个素因数均为这些素数的数。（其中 $1$ 不是丑数）

解题思路

我们假设 $1$ 是第 $0$ 个丑数，这样不会影响答案。
每一次获取新丑数时，遍历所有丑数，将其与 $k$ 个给定素数相乘，取大于上一个丑数的乘积中最小的那个作为取出的新丑数。

优化1

记录每个丑数乘过的最大素数编号，每一次获取新丑数时对记录的素数编号加 $1$ 直到乘积大于上一个丑数，接着将该丑数与下一个素数试乘即可。

优化2

因为同一个素数乘已有丑数并取最小时，一定时选择的已有丑数越靠前，乘积越小，所以对于每一个素数，我们只试乘最靠前的那个可行丑数。
这时候我们可以对每一个素数建立一个队列，用于记录可以乘该素数的丑数编号。（也可以使用链表记录）此时需要做以下改动：

• 初始时将丑数编号 $0$ 入队列 $1$ ；
• 每次获取新丑数后需将使用过的素数的队列队头弹出，若下一个素数编号不超过 $k$ 则入队。

AC 代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5001,mod=1e6+7;
int k,n,a[100001],sum,num[101];
//a[]为求出的丑数，sum为已求出的丑数数量（1除外），num[]表示给定的素数表
queue<int>q[101];//可以乘该素数的丑数编号队列
void makenew(){
    //构造新丑数
    int id=-1;//存储找到的可乘最优丑数编号
    for(int i=1;i<=k;i++){
        while(!q[i].empty()&&num[i]*a[q[i].front()]<=a[sum])q[i].pop();
        //弹出小于上一个丑数的丑数编号
        if(!q[i].empty()&&(id==-1||
            num[i]*a[q[i].front()]<num[id]*a[q[id].front()]))
                id=i;
    }
    sum++,a[sum]=num[id]*a[q[id].front()];//建立新丑数
    q[1].push(sum);
    if(id<k){
        q[id+1].push(q[id].front());
        q[id].pop();//若还可以试乘下一个素数，则放入再弹出
    } else q[id].pop();//否则直接弹出
}
int main(){
    scanf("%d%d",&k,&n);
    for(int i=1;i<=k;i++)
        scanf("%d",num+i);
    a[0]=1;
    q[1].push(0);
    for(int i=1;i<=n;i++){
        makenew();
        // printdata();
    }
    printf("%d\n",a[n]);
    return 0;
}