C++ 快樂數計數優化：預計算 + 空間換時間，解決 500 萬數據超時

問題描述

給定正整數 N (≤ 5,000,000)，計算 [1, N] 中「快樂數」個數。
快樂數定義：對數字各位平方和迭代，最終收斂到 1。否則進入循環（如 4→16→37→58→89→145→42→20→4）。

測試用例 T ≤ 20，單次遍歷 500 萬數字直接模擬會超時。

核心優化洞察

1. 最大位平方和：5,000,000 為 7 位，最大平方和 = 7 × 9² = 567。所有數經過一次變換後均落入 [1, 567] 區間。
2. 預計算 1~567 的快樂數屬性：僅需判斷 567 個數，極快。
3. 查表判斷：對任意 n ≤ 5,000,000，計算一次位平方和 next(n)，查表 isHappy[next(n)] 即知結果。

算法步驟

1. 構建 bool isHappy[568]，標記 1~567 是否為快樂數。
   　　使用 DFS/遞歸 + 訪問標記檢測循環，或 Floyd 判圈算法。
2. 預計算 next[n]（可選，或實時計算）。
3. 對每個測試用例 N，遍歷 1~N，累加 isHappy[next(i)] 為 true 的計數。
4. 更進一步：預計算 prefixHappy[i] = 1~i 快樂數個數，查詢 O(1) 回答。

關鍵代碼（C++）

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

const int MAX_SUM = 7 * 81; // 567
bool isHappy[MAX_SUM + 1];
int prefixHappy[5000001];

int nextNum(int n) {
    int sum = 0;
    while (n) { int d = n % 10; sum += d * d; n /= 10; }
    return sum;
}

void init() {
    // 1. 判斷 1~567 快樂數
    for (int i = 1; i <= MAX_SUM; i++) {
        int slow = i, fast = i;
        do {
            slow = nextNum(slow);
            fast = nextNum(nextNum(fast));
        } while (slow != fast);
        isHappy[i] = (slow == 1);
    }
    // 2. 預計算前綴和
    for (int i = 1; i <= 5000000; i++) {
        prefixHappy[i] = prefixHappy[i-1] + (isHappy[nextNum(i)] ? 1 : 0);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int T; cin >> T;
    while (T--) {
        int N; cin >> N;
        cout << prefixHappy[N] << '\n';
    }
    return 0;
}

複雜度分析

• 預計算：O(MAX_SUM * 迭代次數) + O(5e6) ≈ 幾千萬操作，< 0.1s。
• 查詢：O(1) 每個測試用例。
• 空間：5000001 * 4B ≈ 20MB，符合限制。

關鍵點總結

• 發現「變換後數值域極小」是破解超時的關鍵。
• 空間換時間：前綴和數組將多次查詢降為 O(1)。
• Floyd 判圈算法無需額外訪問數組，代碼極簡。