【题目描述】

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

【题目来源】

刘汝佳《算法竞赛入门经典  第2版》 例题3-5　生成元（Digit Generator, ACM/ICPC Seoul 2005, UVa1583）

【解析】

一、原书代码：

本题的新知识点就是用程序生成一个“查找表”，方法是一次性枚举100000内的所有正整数m，它肯定是“m加上m的各个数字之和（即y）”的一个生成元，所以可以用数组ans[]建立一个查找表，取ans [y]的值为最的小m，即ans[y]的值为y的最小生成元，最后查表即可。

建立查找表的好处就是只需要完整地遍历一次，以后在数据范围内求任何数的最小生成元都能通过查找表快速查找，几乎不需要任何计算。

代码如下：

#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; }
		//取ans[y]的值为最小的m
        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;
}

二、老金代码

老金没想那么多，上来就是“穷举”一波。穷举思路和原书基本一样，代码如下：

#include<stdio.h>
int main(){
    int n;
    scanf("%d", &n);
    for(int i=1; i<n; i++){
        int sum=i, t=i;
        //将数字t分离求和
        while(t){
            sum+=t%10;
            t/=10;
        }
        if(sum==n){
            printf("%d\n", i);
            return 0;
        }
    }
    printf("0\n");
    return 0;
}