# UVa 443 Humble Numbers

###题解 ####解法1 有点暴力。。。 用STL setvector来枚举所有符合条件的数。用long long来防止爆int和栈。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31  #include #include #include using namespace std; typedef long long ll; const int t[] = { 2, 3, 5, 7}; set s; int main(void) { s.insert(1); set::iterator i = s.begin(); while(s.size() < 6600) { for (int j = 0; j < 4; j++) s.insert((*i)*t[j]); i++; } vector v(s.begin(), s.end()); int n; string s; while (cin >> n) { if (n == 0) break; if (n % 100 == 11 || n % 100 == 12 || n % 100 == 13) s = "th"; else if (n % 10 == 1) s = "st"; else if (n % 10 == 2) s = "nd"; else if (n % 10 == 3) s = "rd"; else s = "th"; cout << "The " << n << s << " humble number is " << v[n-1] << ".\n"; } return 0; } 

####解法2 我们有：

a质因子使用的次数，用来生成下一个数
num保存4个质因子生成的数， 找到最小的填入ans数组中
ans打表

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41  #include #include #include #define maxn 5842+5 using namespace std; const int t[] = { 2, 3, 5, 7 }; int a[4] = {1, 1, 1, 1}, num[4], n, ans[maxn]; string s; int find_min() { int Min = num[0]; for (int j = 1; j < 4; j++) { if (Min > num[j]) { Min = num[j]; } } return Min; } int main(void) { int index = 2; ans[1] = 1; while(index < maxn) { for (int i = 0; i < 4; i++) num[i] = ans[a[i]]*t[i]; ans[index] = find_min(); for (int i = 0; i < 4; i++) { if (ans[index] == num[i]) a[i]++; } index++; } while (cin >> n) { if (n == 0) break; if (n % 100 == 11 || n % 100 == 12 || n % 100 == 13) s = "th"; else if (n % 10 == 1) s = "st"; else if (n % 10 == 2) s = "nd"; else if (n % 10 == 3) s = "rd"; else s = "th"; cout << "The " << n << s << " humble number is " << ans[n] << ".\n"; } return 0; }