HDU 1058 Humble Numbers DP生成丑數變體

問題描述

Humble Numbers 定義：質因子只包含 2, 3, 5, 7 的正整數。求第 n 個（n ≤ 5842），並按英文序數詞輸出（如 1st, 2nd, 3rd, 4th, 11th, 12th, 13th, 21st...）。

多指針生成法

維護四個指針 p2, p3, p5, p7，分別指向下一個乘 2/3/5/7 可能產生新 humble number 的位置。
初始 h[1] = 1，四指針均指向 1。
每次取 min(2*h[p2], 3*h[p3], 5*h[p5], 7*h[p7]) 作為下一個 humble number，相應指針++（可能多個相等，全部++）。

代碼實現

int h[5850];
int p2=1, p3=1, p5=1, p7=1;
h[1] = 1;
for (int i = 2; i <= 5842; ++i) {
    h[i] = min({2*h[p2], 3*h[p3], 5*h[p5], 7*h[p7]});
    if (h[i] == 2*h[p2]) ++p2;
    if (h[i] == 3*h[p3]) ++p3;
    if (h[i] == 5*h[p5]) ++p5;
    if (h[i] == 7*h[p7]) ++p7;
}

英文序數詞規則

• 11, 12, 13 → th
• 個位 1 → st（除 11）
• 個位 2 → nd（除 12）
• 個位 3 → rd（除 13）
• 其餘 → th

if (n%100==11 || n%100==12 || n%100==13) suffix = "th";
else if (n%10==1) suffix = "st";
else if (n%10==2) suffix = "nd";
else if (n%10==3) suffix = "rd";
else suffix = "th";

複雜度

預處理 O(N)，查詢 O(1)。N=5842 很小，瞬間完成。