Description
对于一给定的素数集合,来考虑那些质因数全部属于S 的数的集合。寻找集合中的第N个丑数。
Sample Input
4 19
2 3 5 7
Sample Output
27
题解：
时间复杂度o（nlog n）
用一个小根堆就可以解决,注意不要重载long long 或int 的运算符,否则会导致错误.
由小到大生产丑数，我们将生成的丑数存入一个优先队列(小根堆)。
1.设1为丑数，将1出入堆；
2.取出堆顶元素x,将x*p1,x*p2,...,x*pk存入堆中；
3.重复上面的操作，第N+1次取出的堆顶元素，及是所求第N小的丑数
代码：
constmaxn=100;
varn,m:longint;s:array [0..100000] of longint;a:array [1..maxn] of longint;b:array [1..maxn] of longint;
procedure init;var i:longint;beginreadln(m,n);for i:=1 to m dobeginread(a[i]);b[i]:=0;end;end;
procedure main;var i,j,min,t,l:longint;begins[0]:=1; l:=1;for i:=1 to n dobeginwhile 1=1 dobeginmin:=maxlongint; t:=0;for j:=1 to m doif (s[b[j]]*a[j]<min)thenbeginmin:=s[b[j]]*a[j]; t:=j;end;inc(b[t]);if l<>minthen beginbreak;end;end;s[i]:=min; l:=min;end;end;
begininit;main;writeln(s[n]);
end.