描述
如果x加上x的各个数字之和得到y，就说x是y的生成元。给出n（1小于等于n小于等于100000），求最小生成元。无解输出0.例如，n=216，121，2005时的解分别为198，0，1979.
分析
本题看起来是个数学题，但是不然。假设求生成元为m。不难发现m<n.换句话说只要枚举所有的m<n,看看有没有哪个数是n的生成元。 但是这样效率不高，因为每次计算一个n的生成元都需要枚举n-1个数。有没有更加快的方法？只需要一次性枚举100000内的所有正整数m，标记“m加上m各个数字之和得到的数有一个生成元是m”
代码
#include
<stdio
.h
>
#include
<string
.h
>
#define maxn
100005
int ans
[maxn
];
int
main(){
int t
,n
;
meset(ans
,0,sizeof(ans
));
for(int m
=1;m
<maxn
;m
++){
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;
}
