Humble Numbers
For a given set of K prime numbers S = {p1, p2, ..., pK}, consider the set of all numbers whose prime factors are a subset of S. This set contains, for example, p1, p1p2, p1p1, and p1p2p3 (among others). This is the set of `humble numbers' for the input set S. Note: The number 1 is explicitly declared not to be a humble number.
Your job is to find the Nth humble number for a given set S. Long integers (signed 32-bit) will be adequate for all solutions.
PROGRAM NAME: humble
INPUT FORMAT
| Line 1: | Two space separated integers: K and N, 1 <= K <=100 and 1 <= N <= 100,000. |
| Line 2: | K space separated positive integers that comprise the set S. |
SAMPLE INPUT (file humble.in)
4 19
2 3 5 7
OUTPUT FORMAT
The Nth humble number from set S printed alone on a line.
SAMPLE OUTPUT (file humble.out)
27
————————————————————
所以就是一道set的简单应用
然而我的内存在最后一个测试点炸了
事实上操作内存不需要n*k然后第n次的begin，只要不断维护这个序列是n长最后把--end抛出去
然后就没有内存问题了，还会比较快
/*
ID: ivorysi
PROG: humble
LANG: C++
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define sigongzi(j,x,y) for(int j=(x);j>(y);--j)
#define inf 0x7fffffff
#define MAXN 100005
#define ivorysi
using namespace std;
typedef long long ll;
set<int> s;
int n,k,pri[];
void solve() {
scanf("%d%d",&k,&n);
siji(i,,k) {scanf("%d",&pri[i]);s.insert(pri[i]);}
siji(i,,k){
set<int>::iterator k=s.begin();
while() {
int tm=(*k)*pri[i];
if(tm<) break;
if(s.size()>n) {
s.erase(--s.end());
if(tm>(*--s.end()))
break;
}
s.insert(tm);
++k;
}
}
printf("%d\n",*(--s.end()));
}
int main(int argc, char const *argv[])
{
#ifdef ivorysi
freopen("humble.in","r",stdin);
freopen("humble.out","w",stdout);
#else
freopen("f1.in","r",stdin);
#endif
solve();
}