学步园

题意：找出所有因子中只有2,3,5,7的数，给出n，求出第n个这样的数

思路：

每个这样的数都可以表示为num2 * num3 * num5 * num7，其中num i 表示i的一个幂

解释得再清楚些，2^mi2 * 3^mi3 * 5^mi5 * 7^mi7

num2, num3, num5, num7分别从1开始，依次记下小于20亿的乘积，最后对这个数组排序。这就是预处理阶段

后面的大家都会了

总结：11th，而不是11st。32ms

#include <iostream><br /> #include <algorithm><br /> #define F(i,a,b) for (int i=a;i<=b;i++)<br /> #define MAXN 2000000000<br /> using namespace std;</p> <p>int a[6000];</p> <p>int main()<br /> {<br /> // init<br /> unsigned long long num2, num3, num5, num7, temp;<br /> int total = 0, n;<br /> num2 = 1;<br /> while (num2 <= MAXN )<br /> {<br /> num3 = 1;<br /> while (num2 * num3 <= MAXN)<br /> {<br /> num5 = 1;<br /> while ( num2 * num3 * num5 <=MAXN )<br /> {<br /> num7 = 1;<br /> while (num2 * num3 * num5 * num7 <= MAXN )<br /> {<br /> a[ ++ total ] = num2 * num3 * num5 * num7;<br /> num7 *= 7;</p> <p> }<br /> num5 *= 5;<br /> }<br /> num3 *= 3;<br /> }<br /> num2 *= 2;<br /> }<br /> sort(&a[1], &a[total+1] );</p> <p> while (cin >> n && n)<br /> {<br /> if (n%10 == 1 && n%100 != 11)<br /> printf("The %dst humble number is %d./n", n, a[n] );<br /> else<br /> if (n%10 == 2 && n%100 != 12)<br /> printf("The %dnd humble number is %d./n", n, a[n] );<br /> else<br /> if (n%10 == 3 && n%100 != 13)<br /> printf("The %drd humble number is %d./n", n, a[n] );<br /> else<br /> printf("The %dth humble number is %d./n", n, a[n] );<br /> }<br /> return 0;<br /> }