生成元（Digit Generator ，ACM/ICPC Seoul 2005 ,UVa 1583）

生成元：如果 x 加上 x 各个数字之和得到y，则说x是y的生成元。

n（1<=n<=100000）,求最小生成元，无解输出0.

例如：n=216 , 解是：198 

198+1+9+8=216

 

解题思路：打表

循环将从1到10005（大点也可以）进行提前写好。

例如：

1  1+1=2，-->  arr[2]=1

13 13+1+3=17，-->arr[17]=13

34  34+3+4=41， -->arr[41]=34

打完表后，直接将给的数作为下标，输出即可。

#include<stdio.h>
#include<string.h>
#define maxn 100005
int main(void)
{int t,n,i,j,m,ans[maxn];memset(ans,0,sizeof(ans));for(m=1; m<maxn; m++){i=j=m;while(i>0){j+=i%10;i/=10;}if(ans[j]==0||m<ans[j])ans[j]=m;}scanf("%d",&t);while(t--){scanf("%d",&n);printf("%d\n",ans[n]);}return 0;
}

　　 if(ans[j]==0||m<ans[j])ans[j]=m;//如果ans[j]没有被赋值，或者当前的m<ans[j]（写入最小生成元）。