解题思路

这道题要求我们生成Humble数（即质因数只能是2、3、5、7的数），并按顺序找到第$n$个Humble数。由于$n$的范围是$1 \leq n \leq 5842$，我们需要一种高效的方法来生成这些数，避免暴力枚举带来的高时间复杂度。

关键思路

1. 动态规划（DP）+ 多指针法

   • 初始化dp[1] = 1（第一个Humble数是1）。
   • 维护4个指针p2, p3, p5, p7，分别表示当前应该乘以2、3、5、7的最小Humble数的位置。
   • 每次计算dp[i] = min(dp[p2]*2, dp[p3]*3, dp[p5]*5, dp[p7]*7)，并更新对应的指针（如果某个指针生成的数被选中，则指针后移）。
   • 这样可以保证dp数组按升序填充，且每个Humble数只计算一次。

2. 处理序数后缀（"st", "nd", "rd", "th"）

   • 注意特殊情况（如11、12、13等以"th"结尾）。
   • 其他情况下，根据个位数决定后缀。

C++ 实现

#include <iostream>
#include <vector>
#include <algorithm>  // 包含 min 函数

using namespace std;

vector<long long> generateHumbleNumbers(int maxN) {
    vector<long long> dp(maxN + 1);
    dp[1] = 1;
    int p2 = 1, p3 = 1, p5 = 1, p7 = 1;
    for (int i = 2; i <= maxN; i++) {
        long long nextNum = dp[p2] * 2;
        nextNum = min(nextNum, dp[p3] * 3);
        nextNum = min(nextNum, dp[p5] * 5);
        nextNum = min(nextNum, dp[p7] * 7);
        dp[i] = nextNum;
        if (nextNum == dp[p2] * 2) p2++;
        if (nextNum == dp[p3] * 3) p3++;
        if (nextNum == dp[p5] * 5) p5++;
        if (nextNum == dp[p7] * 7) p7++;
    }
    return dp;
}

string getSuffix(int n) {
    if (n % 100 >= 11 && n % 100 <= 13) {
        return "th";
    }
    switch (n % 10) {
        case 1: return "st";
        case 2: return "nd";
        case 3: return "rd";
        default: return "th";
    }
}

int main() {
    const int MAX_N = 5842;
    vector<long long> humbleNumbers = generateHumbleNumbers(MAX_N);
    
    int n;
    while (cin >> n && n != 0) {
        string suffix = getSuffix(n);
        cout << "The " << n << suffix << " humble number is " << humbleNumbers[n] << "." << endl;
    }
    
    return 0;
}