【描述】
对于一给定的素数集合 S = {p1, p2, ..., pK},
来考虑那些质因数全部属于S 的数的集合。这个集合包括，p1, p1p2, p1p1, 和 p1p2p3 (还有其它)。这是个对于一个输入的S的丑数集合。
注意：我们不认为1 是一个丑数。
你的工作是对于输入的集合S去寻找集合中的第N个丑数。longint(signed 32-bit)对于程序是足够的。
来考虑那些质因数全部属于S 的数的集合。这个集合包括，p1, p1p2, p1p1, 和 p1p2p3 (还有其它)。这是个对于一个输入的S的丑数集合。
注意：我们不认为1 是一个丑数。
你的工作是对于输入的集合S去寻找集合中的第N个丑数。longint(signed 32-bit)对于程序是足够的。
【格式】
PROGRAM NAME: humble
INPUT FORMAT:(file humble.in)
| 第 1 行: | 二个被空间分开的整数:K 和 N ， 1<= K<=100 ， 1<= N<=100,000. |
| 第 2 行: | K 个被空间分开的整数:集合S的元素 |
OUTPUT FORMAT:(file humble.out)
单独的一行，写上对于输入的S的第N个丑数。
【分析】
不说什么了，原题，直接上代码。
#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
typedef long long ll;
const ll maxn=+;
const ll maxk=;
using namespace std;
ll S[maxk],N[maxn],low[maxn];
//low用来加速
int main()
{
ll k,n,i,j,l,minp=;
//文件操作
freopen("humble.in","r",stdin);
freopen("humble.out","w",stdout);
memset(low,,sizeof(low));
scanf("%lld%lld",&k,&n);
for (i=;i<=k;i++) scanf("%lld",&S[i]);
sort(S+,S++k);//排序
N[]=;//初始化
for (i=;i<=n;i++)//求第I个丑数
{
ll temp=0x7fffffff;
for (j=;j<=k;j++)
{
while (S[j]*N[low[j]]<=N[i-]) low[j]++;
if (S[j]*N[low[j]]<temp)
{
temp=S[j]*N[low[j]];
minp=j;
}
}
N[i]=temp;
low[minp]++;
}
printf("%lld",N[n]);
return ;
}