每次找下一个最小的humble数直到第n个为止。
对每一个prime，用二分法找出乘以已有的humble数且>=现有最大的humble数的最小的那一个。
然后取最小的那一个作为新找到的humble数。
开始的时候最后一个例子总是超时，后来用一个next_min数组缓存一下结果，效率一下提高了10倍。
#include <iostream>
#include <fstream>
using namespace std;
int humbles[100002];
int primes[100];
int k,n;
int top;
int next_min[100];
long long find_next(int i)
{
int l = 0;
int h = top;
int mid;
while(l<=h){
mid = (l+h)/2;
if((long long)humbles[mid]*primes[i]<=humbles[top]){
l = mid+1;
}else{
h = mid-1;
}
}
return humbles[h+1]*primes[i];
}
void solve()
{
humbles[0] = 1;
top = 0;
freopen("humble.in","r",stdin);
freopen("humble.out","w",stdout);
scanf("%d%d",&k,&n);
for(int i=0;i<k;++i)
scanf("%d",&primes[i]);
for(int i=0;i<k;++i)
next_min[i] = find_next(i);
while(top<n){
long long next = LONG_MAX;
long long tmp;
for(int i=0;i<k;++i){
if(next_min[i]<=humbles[top])
tmp = next_min[i] = find_next(i);
else
tmp = next_min[i];
if(tmp<next){
next = tmp;
}
if(next==humbles[top]+1)
break;
}
humbles[++top] = next;
}
printf("%d\n",humbles[n]);
}
int main(int argc,char *argv[])
{
solve();
return 0;
}