Humble Numbers
题意： 如果一个数的质因子只有2，3，5，7，那么这个数就叫“丑数”，下现在要求前5842个“丑数”。
分析： 根据质因子分解唯一，我们知道只需要将 1分别乘上2，3，5，7，然后将得到的数在进行这样子的操作，由于原数列是递增排列的，所以可以使用优先队列维护。（在HDU上打表用了97ms，但是Vj上貌似不让交这么长的代码）
代码如下：
#include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <cctype> #include <fstream> #define INF 0x3f3f3f3f #define TEST cout<<"stop here"<<endl using namespace std; typedef long long ll; const ll mod = 1e9 + 7; ll num[5900]; int main(){ std::ios::sync_with_stdio(false); std::cin.tie(0); /* ofstream outfile; outfile.open("data.txt"); ll j=1; outfile<<"{"<<" "; for(ll i=1;i<=2000000000;i++){ if(judge(i)) {outfile<< i << ','<<" ";j++;} if(j==20){outfile<<endl;j=1;} } outfile<<"}"<<endl; outfile.close(); */ ll tmp = 1; priority_queue<ll, vector<ll>, greater<ll> > que; int i = 1; while(i<=5842){ que.push(1); while(!que.empty()){ if(i>5842) break; tmp = que.top(); que.pop(); if(tmp!=num[i-1]){ num[i++] = tmp; que.push(tmp*2); que.push(tmp*3); que.push(tmp*5); que.push(tmp*7); } } } int n; while(cin>>n && n){ if(n%10==1 && n%100 != 11) printf("The %dst humble number is %lld.\n",n,num[n]); else if(n%10==2 && n%100!=12) printf("The %dnd humble number is %lld.\n",n,num[n]); else if(n%10==3 && n%100!=13) printf("The %drd humble number is %lld.\n",n,num[n]); else printf("The %dth humble number is %lld.\n",n,num[n]); } return 0; }