1126 丑数.md

1126

Description

对于一给定的素数集合 S = {p1, p2, ..., pK},如果一个数字，当我们对其做完质因子分解后，其质因子全是来自我们给定的素数集合，则认为这个数字是个丑数。
注意：我们不认为1 是一个丑数。
你的工作是对于输入的集合S去寻找第N个丑数。

Input

第 1 行: 二个被空间分开的整数:K 和 N ， 1<= K<=100 ， 1<= N<=100,000.
第 2 行: K 个被空间分开的整数:集合S的元素

Output

第N个丑数。

Sample Input

4 19
2 3 5 7

Sample Output

27

HINT

视频讲解在:http://begin.lydsy.com/JudgeOnline/upload/1126.avi

---

#include<bits/stdc++.h>
using namespace std;
int k,n,f[1001],c[1000001],ans[1000001];
int main() {
 
    cin>>k>>n;
    ans[1]=1;
    for(int i=1; i<=k; i++) {
        cin>>f[i];
        c[i]=1;
    }
    for(int j=2; j<=n+1; j++) {
        int min;
        min=2147480000;
        for(int b=1;b<=k;b++) {
            if(f[b]*ans[c[b]]<min)
                min=f[b]*ans[c[b]];
        }
        ans[j]=min;
        for(int b=1; b<=k; b++) {
            if(min==f[b]*ans[c[b]])
                c[b]++;
        }
    }
    cout<<ans[n+1];
    return 0;
}