算法之路二：刘汝佳算法竞赛入门经典 3.9生成元 UVa1583

#include<stdio.h>
#include<string.h>
#define maxn 100005
int ans[maxn];

int main()
{
    int T,n;
    memset(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;//从1-maxn找每个数最小生成元，没有为0 
    }
    scanf("%d",&T);
    while(T--)//输入T个数 
    {
        scanf("%d",&n);
        printf("%d\n",ans[n]);//输出每个数的最小生成元 
    }
    return 0;
 } 

//每次计算一个n的生成元都需要枚举n-1个数
先一次枚举出100000内所有，在查表更快！！