UVa 11032 Function Overloading：sod 函數與預處理答案

問題描述

定義 sod(n) 為 n 的各位數字之和。兩個重載函數：
1. fun(a, b)：返回區間 [a,b] 中「無生成元」的數的個數（即不存在 x 使得 x + sod(x) = i）。
2. fun(a)：返回最小的 x 使得 x + sod(x) = a，不存在返回 -1。
輸入多組測試，每行 1 或 2 個整數（≤ 10⁷），輸出對應函數值。

核心觀察

• x + sod(x) 的最大增量：對於 10⁷，sod(x) ≤ 9×8=72。故 x + sod(x) 至多比 x 大 72。
• 可預處理所有 1~10⁷+72 的「生成元」情況。
    建立數組 gen[val] = 最小的 x 使得 x + sod(x) = val（不存在為 -1）。
    再建前綴和 cnt[i] = [1..i] 中無生成元的數的個數。
  則 fun(a,b) = cnt[b] - cnt[a-1]，fun(a) = gen[a]。

預處理算法

const int MAXV = 10000000 + 72;
int gen[MAXV]; // 生成元，-1 表示無
int cnt[MAXV]; // 前綴無生成元計數
int sod(int x) { int s=0; while(x){ s+=x%10; x/=10; } return s; }
void init() {
    fill(gen, gen+MAXV, -1);
    for (int i = 1; i < MAXV; ++i) {
        int v = i + sod(i);
        if (v < MAXV && gen[v] == -1) gen[v] = i;
    }
    for (int i = 1; i < MAXV; ++i) {
        cnt[i] = cnt[i-1] + (gen[i] == -1);
    }
}

代碼實現 (C++)

#include <bits/stdc++.h>
using namespace std;
const int MAXV = 10000072;
int gen[MAXV], cnt[MAXV];
int sod(int x) { int s=0; while(x){ s+=x%10; x/=10; } return s; }
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    fill(gen, gen+MAXV, -1);
    for (int i = 1; i < MAXV; ++i) {
        int v = i + sod(i);
        if (v < MAXV && gen[v] == -1) gen[v] = i;
    }
    for (int i = 1; i < MAXV; ++i) cnt[i] = cnt[i-1] + (gen[i] == -1);
    int T; cin >> T;
    string line; getline(cin, line); // 吃掉換行
    for (int tc = 1; tc <= T; ++tc) {
        getline(cin, line);
        stringstream ss(line);
        vector nums;
        int x;
        while (ss >> x) nums.push_back(x);
        if (nums.size() == 1) {
            cout << "Case " << tc << ": " << gen[nums[0]] << '\n';
        } else {
            int a = nums[0], b = nums[1];
            if (a > b) swap(a, b);
            cout << "Case " << tc << ": " << cnt[b] - cnt[a-1] << '\n';
        }
    }
    return 0;
}

複雜度

• 預處理：O(MAXV × 位數) ≈ 7×10⁷ 操作，約 0.5 秒內完成。
• 查詢：O(1)。
• 空間：兩個 int 數組 ≈ 80 MB，略大但可接受（可用 short 或 vector 優化）。

關鍵點

• 利用 sod(x) 有界性，將問題轉化為「每個數是否被生成」的標記問題。
• 預處理 + 前綴和，多查詢 O(1) 響應。
• 注意輸入格式：每行 1 或 2 個數，需按行讀取並解析。

這題展示了「預處理換查詢時間」的經典思想，將看似複雜的數論函數通過有界性轉化為簡單的陣列標記。