1583 - Digit Generator

Problem.png

输入一个数，找出这个数的最小生成元。
生成元的意思是：一个整数，比如245，它本身加上它各位数之和等于256 (= 245 + 2 + 4 + 5)，则245就是256的一个生成元。
这题有一个笨办法是对每一个输入整数N，枚举小于N的所有数，看他们是否是N的生成元，这种方法显然耗时太多。
有一个比较巧妙的方法是，题中的N最大值为100000，则我们对0~100000范围内的所有数，计算它们能成为哪些数的生成元(即能生成哪些数)，以那些数为数组的索引，值为对应的生成元建立映射，则遍历一遍十万个数，就能建立一个映射数组，后面只需要按照输入来查表即可。

这种技巧感觉挺重要，对于某类映射问题，可以先枚举所有数造一个映射表，后面只需按照输入查表，可以节约很多时间。

#include <iostream>

using namespace std;

int gen[110000] = {0};

int main() {
    int T;
    cin >> T;
    for (int i = 100000; i >= 0; i--) {
        int sum = i, d = i;
        while (d) {
            sum += d % 10;
            d /= 10;
        }
        gen[sum] = i;
    }
    while (T) {
        int num;
        cin >> num;
        cout << gen[num] << endl;
        T--;
    }
}

另外还要注意，本题是求最小生成元，因此从大到小枚举所有数，让新算出来的较小的生成元覆盖掉旧的较大的生成元，从而最终得到的是最小生成元。