题海拾贝——生成元（Digit Generator,ACM/ICPC SEOUL 2005,UVa1583）

        Hello大家好！很高兴我们又见面啦！给生活添点passion，开始今天的编程之路！

我的博客：<但凡.

欢迎点赞关注！

1、题目描述

        如果x加上x的各个数字之和得到y，就说x是y的生成元。给出(1<=n<=100000),求最小生成元。无解输出0。

2、思路分析

       我们首先想到的是遍历每个数， 找出他们的最小生成数。但这样的话如果我要求找五个数的最小生成数呢？我们就得遍历5次，显然这样效率不够高。所以我们不如索性一次性找到所有数的最小生成元，然后存放起来，最后查表即可。

3、题解

#include<stdio.h>
#define maxn 100000
int main()
{
    int T = 0;
    int m = 0;
    int arr[maxn] = { 0 };//初始化存放被生成数的数组
    int x = 0;
    int y = 0;
    //找出所有属于1——10000这个范围的被生成数，并记录他们的最小生成元
    for (m = 0;m < maxn;m++)//循环存入所有被生成数的最小生成元
    {
        x = m;y = m;
        while (x)//计算被生成数
        {
            y +=x % 10;
            x /= 10;
        }
        if (arr[y]==0||m<arr[y])//条件为当这个元素为0或新的被存入元素(生成元)更小
        {
            arr[y] = m;//记录这个被生成数y的最小生成元
        }
    }
    //输入要查找最小生成元的次数
    scanf_s("%d", &T);
    while (T)
    {
        //输入想要查找的元素
        scanf_s("%d", &y);
        printf("%d\n", arr[y]);
        T--;
    }
    return 0;
}

       今天的内容就分享到这，我们下期再见！