【算法竞赛入门经典】第三章-生成元

题干：如果x加上x的各个数字之和得到y，就说x是y的生成元。给出n（1≤n≤100000），求最小生成元。无解输出0.例如，n=216,121,2005时的解分别为198,0,1979

思路：本人一开始看到这题时首先想到了枚举（好吧大家都能想到），但本书提供了一种奇妙的方法：做表。

#include<stdio.h>
#include<string.h>
#define maxn 100005
int arr[maxn];
int main()
{
	int T,n;
	memset(arr,0,sizeof(arr));
	for(int i=0;i<maxn;i++)//做表 
	{
		int x = i;
		int y = i;
		while(x>0)
		{
			y+=x%10;
			x/=10;
		}//y是i生成的数
		if(arr[y]==0 || i<arr[y])//其实i<arr[y]应该是为了加强程序的鲁棒性，不写的话问题不大 
		arr[y] = i; //用数组第y个元素存储第y个元素的生成元 ，然后由生成元找第y个元素 
	}
	scanf("%d",&n);
	printf("%d",arr[n]);
	return 0 ; 
	
}