ZeroJudge 解題筆記：c122. 00443 - Humble Numbers

作者：王一哲
日期：2026年3月15日


ZeroJudge 題目連結：c122. 00443 - Humble Numbers

解題想法

用陣列 nums 儲存 humble number，再用另外 4 個變數 i2, i3, i5, i7 記錄 nums 之中前一個 2、3、5、7 倍數對應的索引值，每次更新時計算這 4 個索引值分別乘以 2、3、5、7 的值，取其中的最小值加入 nums 之中並更新對應的索引值，當 nums 的長度等於 5842 就可以停止運算。接下來讀取測資，從 nums 之中找答案。

Python 程式碼

使用時間約為 14 ms，記憶體約為 4.6 MB，通過測試。

import sys

# 計算前 5842 個Humble Number
nums = [0, 1]  # 配合編號，開頭多一個 0
i2, i3, i5, i7 = 1, 1, 1, 1  # 2, 3, 5, 7 倍數基底的索引值
while len(nums) <= 5842:  # 當 nums 長度小於、等於 5842 時繼續執行
    nxt2 = nums[i2] * 2  # 下一個 2 的倍數
    nxt3 = nums[i3] * 3  # 下一個 3 的倍數
    nxt5 = nums[i5] * 5  # 下一個 5 的倍數
    nxt7 = nums[i7] * 7  # 下一個 7 的倍數
    nxt_num = min(nxt2, nxt3, nxt5, nxt7)  # 取以上 4 個數之中的最小值加入 nums
    nums.append(nxt_num)
    if nxt_num == nxt2: i2 += 1  # 如果是 2 的倍數更新 i2
    if nxt_num == nxt3: i3 += 1  # 如果是 3 的倍數更新 i3
    if nxt_num == nxt5: i5 += 1  # 如果是 5 的倍數更新 i5
    if nxt_num == nxt7: i7 += 1  # 如果是 7 的倍數更新 i7

def last(x):  # 數字後面接的英文
     two = x%100  # 最後兩位數
     one = x%10  # 最後一位數
     if two == 11 or two == 12 or two == 13: return "th"  # 最後兩位數是 11、12、13，回傳 th
     if one == 1: return "st"  # 最後一位數是 1，回傳 st
     if one == 2: return "nd"  # 最後一位數是 2，回傳 nd
     if one == 3: return "rd"  # 最後一位數是 3，回傳 rd
     return "th"  # 其它，回傳 th

result = []
lines = sys.stdin.readlines()
for line in lines:
    if not line.strip(): continue
    n = int(line)
    if n == 0: break
    result.append(f"The {n:d}{last(n):s} humble number is {nums[n]:d}.\n")
sys.stdout.write("".join(result))

C++ 程式碼

使用時間約為 1 ms，記憶體約為 408 kB，通過測試。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

string last(int n) {
    int two = n%100, one = n%10;
    if (two == 11 || two == 12 || two == 13) return "th";
    if (one == 1) return "st";
    if (one == 2) return "nd";
    if (one == 3) return "rd";
    return "th";
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    vector<int> nums = {0, 1};
    int i2 = 1, i3 = 1, i5 = 1, i7 = 1;
    while((int)nums.size() <= 5842) {
        int nxt2 = nums[i2]*2, nxt3 = nums[i3]*3, nxt5 = nums[i5]*5, nxt7 = nums[i7]*7;
        int nxt_num = min(nxt2, min(nxt3, min(nxt5, nxt7)));
        nums.push_back(nxt_num);
        if (nxt_num == nxt2) i2++;
        if (nxt_num == nxt3) i3++;
        if (nxt_num == nxt5) i5++;
        if (nxt_num == nxt7) i7++;
    }
    int n;
    while(cin >> n && n != 0) {
        cout << "The " << n << last(n) << " humble number is " << nums[n] << ".\n";
    }
    return 0;
}