UVa1583生成元（Digit Generator）

题目

       如果x加上x的各个数字之和得到y，也就是说x是y的生成元。给出n(1<=n<=100000)，求最小生成元。无解则输出0。

输入输出样例

输入

3
216
121
2005

输出 

198
0
1979

思路

       要想解决这个题目，只需要对每一个输入的值从1开始遍历找到小于它自身的生成元取最小的即可，但是这样的话每一个输入都需要枚举一次，效率太低。更好的方法是我们一次性把1到100000内的所有正整数的最小生成元都求出来，然后对于每一个输入，直接查表即可。 

代码

#include<stdio.h>
#include<string.h>
#define maxn 100005//大小比较大的数组定义在主函数外面，防止出现异常
int ans[maxn];
int main(){
	int T,n;
	memset(ans,0,sizeof(ans));//将数组每一个的值初始化为0 
	int m=1;
	for(m=1;m<maxn;m++){//计算1到100000内的所有整数的最小生成元 
		int x=m,y=m;
		while(x>0){
			y+=x%10;
			x/=10;
		}
		if(ans[y]==0||m<ans[y]){//如果当前数的生成元还没有计算，或者后面计算出来的生成元比目前的生成元小，那么改为当前值 
			ans[y]=m;
		}
	}
	//接下来对于各种输入，直接查表即可 
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		printf("%d\n",ans[n]);
	}
	return 0;
} 

   这个题目的重点就是打表法的使用。