HDU 1197 Specialized Four-Digit Numbers：進制數位和枚舉

問題描述

找出所有四位十進制數（1000~9999），滿足：其十進制數位和、十二進制數位和、十六進制數位和三者相等。無輸入，直接輸出所有符合條件的數，每行一個，遞增順序。

核心思路

暴力枚舉 1000 到 9999，對每個數分別計算三種進制下的數位和，判斷是否相等。數據量極小（9000 個數），直接計算即可，無需優化。

數位和計算函數

int digitSum(int n, int base) {
    int sum = 0;
    while (n) {
        sum += n % base;
        n /= base;
    }
    return sum;
}

完整代碼

#include <bits/stdc++.h>
using namespace std;

int digitSum(int n, int base) {
    int s = 0;
    while (n) { s += n % base; n /= base; }
    return s;
}

int main() {
    for (int x = 1000; x < 10000; ++x) {
        int s10 = digitSum(x, 10);
        int s12 = digitSum(x, 12);
        int s16 = digitSum(x, 16);
        if (s10 == s12 && s12 == s16) {
            cout << x << '\n';
        }
    }
    return 0;
}

輸出前幾行（樣例）

2992
2993
2994
2995
2996
2997
2998
2999
...

複雜度分析

時間：9000 × (log₁₀ + log₁₂ + log₁₆) ≈ 9000 × 12 ≈ 10⁵ 操作，瞬間完成。
空間：O(1)。

拓展思考

• 若擴展到更大範圍（如 10⁹），需用數位 DP 或數學規律優化。
• 本題屬於「輸出型」題目，無輸入，預計算輸出或在線計算均可。