问题描述
如果x加上x的各个数字之和得到y，就说x是y的生成元。给出n（1≤n≤100000），求最小生成元。无解输出0。例如，n=216，121，2005时的解分别为198，0，1979。
思想
若x为y的生成元，则x < y，所以只需要枚举所有的x，寻找最小生成元即可，但这是一个麻烦的做法，因为对与每一个n，需要进行n - 1次运算才能找到最小生成元。
另一个效率更高的办法是，一次性枚举100000内所有数的最小生成元，建立一个数组，最后只要查数组就能找到最小生成元。
先建立一个用来存放生成元的线性表，用数组ans来存放，ans[m] = y就表示m的生成元是y。
由于要找出最小生成元，所以计算出来的某个数的生成元只将最小的存入。
所以步骤可以归纳为：
- 第一步：建立生成元数组
- 第二步：查表即可
代码
在vs2017上运行通过
#include <stdio.h>
#include <string.h>
#define maxn 100005
int ans[maxn];
int main()
{
memset(ans, 0, sizeof(ans)); //置为0表示不存在生成元
//建立生成元数组
for (int i = 0; i < maxn; i++)
{//求i是那个数字所对应的生成元（y）
int x = i, y = i;
while (x)
{
y += x % 10;
x /= 10;
}
if (ans[y] == 0 || ans[y] > i) ans[y] = i; // 因为要求最小生成元
}
//查表输出
int C, n;
scanf("%d", &C);
while (C--)
{
scanf("%d", &n);
printf("%d\n", ans[n]);
}
return 0;
}
