题意：给你k（≤100）个质数，求质因子只包含它们的第n大的数。
题解：
方法一：维护一个数组，一开始只有给出的质数在里面，用每个质数去乘以数组中每个数，然后归并排序，长度保留到n，一轮接一轮，直到乘出来的新出现的数大于原来最大的数，那么如果当前是用最小的质数都没产生新的前n大的数，那么第n个数就是第n大的数。否则跳转到用最小的质数去乘。具体见代码。
/* TASK: humble LANG: C++ */ #include<cstdio> #include<algorithm> #include<iostream> #define N 100005 #define ll long long using namespace std; int n,k,p[N]; ll a[N],b[N],c[N]; bool merge(ll a[],ll b[]){ bool f=0; for(int k=1,i=1,j=1;k<=n;k++) if(!b[j]||a[i]&&a[i]<=b[j]){ c[k]=a[i]; if(a[i]==b[j])j++; i++; }else{ f=1; c[k]=b[j]; j++; } for(int i=1;i<=n&&c[i];i++)a[i]=c[i]; return f; } ll solve(){ while(1){ for(int i=1;i<=k;i++){ for(int j=1;j<=n;j++){ a[j]=p[i]*b[j]; if(b[j]==0||b[n]&&a[j]>b[n])break; } if(!merge(b,a)){ if(i==1)return b[n]; else i=0; } } } } int main(){ freopen("humble.in","r",stdin); freopen("humble.out","w",stdout); scanf("%d%d",&k,&n); for(int i=1;i<=k;i++){ scanf("%d",&p[i]); b[i]=p[i]; } printf("%d ",solve()); return 0; } /* Test 1: TEST OK [0.000 secs, 6912 KB] Test 2: TEST OK [0.000 secs, 6912 KB] Test 3: TEST OK [0.000 secs, 6912 KB] Test 4: TEST OK [0.011 secs, 6912 KB] Test 5: TEST OK [0.043 secs, 6912 KB] Test 6: TEST OK [0.151 secs, 6912 KB] Test 7: TEST OK [0.032 secs, 6912 KB] Test 8: TEST OK [0.032 secs, 6912 KB] Test 9: TEST OK [0.000 secs, 6912 KB] Test 10: TEST OK [0.000 secs, 6912 KB] Test 11: TEST OK [0.000 secs, 6912 KB] Test 12: TEST OK [0.205 secs, 6912 KB] */
方法二：用set，对于每个质数，与set中最小的的乘积插入set，set中维护至多n个元素，然后迭代器后移，直到乘出来的数比最大的数还大或者超出long long就跳出，set中第n个即最大的就是答案。
/* TASK: humble LANG: C++ */ #include<cstdio> #include<algorithm> #include<iostream> #define N 105 #define ll long long #include<set> using namespace std; int n,k,p[N]; set<ll>s; int main(){ freopen("humble.in","r",stdin); freopen("humble.out","w",stdout); cin>>k>>n; for(int i=1;i<=k;i++){ cin>>p[i]; s.insert(p[i]); } set<ll>::iterator it; for(int i=1;i<=k;i++){ it=s.begin(); while(1){ ll t=*it*p[i]; if(t<0)break; if(s.size()>n){ s.erase(--s.end()); if(t>(*--s.end()))break; } s.insert(t); it++; } } cout<<*(--s.end())<<endl; return 0; } /* Test 1: TEST OK [0.000 secs, 4184 KB] Test 2: TEST OK [0.000 secs, 4184 KB] Test 3: TEST OK [0.000 secs, 4184 KB] Test 4: TEST OK [0.011 secs, 4448 KB] Test 5: TEST OK [0.032 secs, 4844 KB] Test 6: TEST OK [0.151 secs, 7220 KB] Test 7: TEST OK [0.043 secs, 5108 KB] Test 8: TEST OK [0.032 secs, 4976 KB] Test 9: TEST OK [0.000 secs, 4184 KB] Test 10: TEST OK [0.000 secs, 4184 KB] Test 11: TEST OK [0.000 secs, 4184 KB] Test 12: TEST OK [0.216 secs, 7220 KB] */
方法三：超时一个点。用优先队列的小根堆即
priority_queue<ll,vector<ll>,greater<ll> >q;
每次用队首乘上每个质数并插入小根堆，并队首出队。第n个出队的就是答案，并且要进行判重，t=q.top()*p[j]; if(ans[i]<t){ans[++i]=t;...}。
方法四：官方题解，用d[i]记录第i个质数要乘到第几个丑数，每次把每个质数和要乘的丑数的乘积的最小值作为新加的丑数，每个质数要乘的丑数就是满足和它相乘后，比最后一个丑数大的最小的丑数。
/* TASK: humble LANG: C++ */ #include<cstdio> #include<algorithm> #include<iostream> #define N 100005 #define ll long long using namespace std; int n,k,p[105]; ll hum[N],d[N]; int main(){ freopen("humble.in","r",stdin); freopen("humble.out","w",stdout); scanf("%d%d",&k,&n); for(int i=1;i<=k;i++) scanf("%d",&p[i]); hum[0]=1; for(int i=1;i<=n;i++){ ll m=hum[i-1]*p[1]; for(int j=1;j<=k;j++){ while(hum[d[j]]*p[j]<=hum[i-1])d[j]++; if(m>hum[d[j]]*p[j])m=hum[d[j]]*p[j]; } hum[i]=m; } printf("%lld ",hum[n]); return 0; } /* Test 1: TEST OK [0.000 secs, 5740 KB] Test 2: TEST OK [0.000 secs, 5740 KB] Test 3: TEST OK [0.000 secs, 5740 KB] Test 4: TEST OK [0.000 secs, 5740 KB] Test 5: TEST OK [0.000 secs, 5740 KB] Test 6: TEST OK [0.022 secs, 5740 KB] Test 7: TEST OK [0.000 secs, 5740 KB] Test 8: TEST OK [0.000 secs, 5740 KB] Test 9: TEST OK [0.000 secs, 5740 KB] Test 10: TEST OK [0.000 secs, 5740 KB] Test 11: TEST OK [0.000 secs, 5740 KB] Test 12: TEST OK [0.108 secs, 5740 KB] */