1.题目大意
如果a加上a的各个数字之和得到b，则说a是b的生成元。给出n其中$1\le n\le 100000$，求其最小生成元，若没有解则输出0。
2.思路
使用打表的方法打出各个数字a对应的b，存入s[b]中。
3.应注意的问题
(1) 没有解时输出0，也就意味着在开始打表前要把数组s[maxn]清零。利用memset实现，要加入string.h的头文件，而memset对数组操作时只能初始化为0或-1。
(2) 要求求出的是最小生成元，也就意味着在存入s[b]之前要有所比较。
4.代码
#include"stdio.h"
#include"string.h"
#define maxn 100005
int s[maxn];
int main()
{
int i,T,n,a,b;
memset(s,0,sizeof(s)); //数组清零
for(i = 1; i < maxn ; i++)
{
a = i;
b = i;
while(a > 0) //原数加上其各个数字之和得到a
{
b += a%10;
a /= 10;
}
if((s[b]==0) || (s[b]>i)) //确保其是最小生成元
s[b] = i;
}
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
printf("%d\n",s[n]);
}
return 0;
}
参考书目：算法竞赛入门经典（第2版） 刘汝佳 编著