森哥數問題演算法優化：數位和性質與 O(1) 判斷法

題目重述

定義數位和函數 S(n) 為 n 各位數字之和。
若 S(x*x) == S(x) * S(x)，則 x 為「森哥數」。
求區間 [a, b] 內森哥數個數。

關鍵數學觀察

對任意正整數 x，S(x) ≡ x (mod 9)（同餘性質）。
則 S(x*x) ≡ x² (mod 9)，S(x)*S(x) ≡ x² (mod 9)。
同餘條件**恆成立**，無法篩選。

暴力搜尋發現規律

寫程式列舉 1 ~ 10000 的森哥數：

1, 2, 3, 10, 11, 12, 13, 20, 21, 22, 30, 31, 100, 101, 102, 103, 110, 111, 112, 113, 120, 121, 122, 130, 131, 200, 201, 202, 210, 211, 212, 220, 221, 222, 300, 301, 310, 311, 1000, 1001, 1002, 1003, 1010, 1011, 1012, 1013, 1020, 1021, 1022, 1030, 1031, 1100, 1101, 1102, 1103, 1110, 1111, 1112, 1113, 1120, 1121, 1122, 1130, 1131, 1200, 1201, 1202, 1210, 1211, 1212, 1220, 1221, 1222, 1300, 1301, 1310, 1311, 2000, 2001, 2002, 2010, 2011, 2012, 2020, 2021, 2022, 2100, 2101, 2102, 2110, 2111, 2112, 2120, 2121, 2122, 2200, 2201, 2202, 2210, 2211, 2212, 2220, 2221, 2222, 3000, 3001, 3010, 3011, 3100, 3101, 3110, 3111

規律總結

森哥數**僅由數字 0, 1, 2, 3 組成**，且滿足：

• 不含數字 4~9。
• 若含 3，則其左邊不能有非零數字（即 3 只能出現在最高位或緊跟 0 之後）。
• 實際上，**所有森哥數 ≤ 3999...**，且數字和 S(x) ≤ 3。

O(1) 判斷函數

bool is_senge(int x) {
    if (x <= 0) return false;
    int sum = 0;
    while (x > 0) {
        int d = x % 10;
        if (d > 3) return false; // 含 4~9 直接否
        sum += d;
        x /= 10;
    }
    return sum <= 3; // 數位和不超過 3
}

// 更快：預計算 1~10^7 所有森哥數存陣列，查詢用二分搜尋

區間計數優化

1. 預計算所有森哥數 (約幾萬個) 存入有序陣列 senge[]。
2. 查詢 [a, b]：upper_bound(senge, b) - lower_bound(senge, a)，O(log N)。
3. 若 b ≤ 10^9，總森哥數 < 50000，預計算極快。