{{{ #!cplusplus /* hdu1058 Humble Numbers DP ymc 2008/9/23 题目大意: 如果一个数的没有2,3,5,7以外的质因子,则这个数 称为Humble数。前几个Humble数为 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, ... 求第n个Humble数。 分析与解题思路: Humble数没有2,3,5,7以外的质因子,则 令h[]记录已经求到的Humble数,假设已经求了num个。 则把所有h[]中的数乘以2,3,5,7得到的最小大于h[num]的 数就是下一个Humble数。但这样无疑会TLE。 Prim[4]={2,3,5,7} 初始id[4]={1,1,1,1} 其中id[k]为h[]中的下标。表示乘以2的Humble数在h[]中的下标。 已经知道num个Humble数时,min{Prim[k]*H[id[k]},0<=k<=3, 就是要找的下一个Humble数。 注意重复的情况。 */ #include #include using namespace std; const int N=5843; int num; double Prim[4]={2,3,5,7}; int id[4]={1,1,1,1};//初始下标 int h[N]; char s[4][3]={"th","st","nd","rd"}; int Humble()//求下一个Humble数, { double Max=INT_MAX;//double类型,乘积可能会超出int。 double tmp; int k; for(int i=0;i<4;i++) { tmp=Prim[i]*h[id[i]]; if(tmp