问题描述

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

思想

若x为y的生成元，则x < y，所以只需要枚举所有的x，寻找最小生成元即可，但这是一个麻烦的做法，因为对与每一个n，需要进行n - 1次运算才能找到最小生成元。

另一个效率更高的办法是，一次性枚举100000内所有数的最小生成元，建立一个数组，最后只要查数组就能找到最小生成元。

先建立一个用来存放生成元的线性表，用数组ans来存放，ans[m] = y就表示m的生成元是y。

由于要找出最小生成元，所以计算出来的某个数的生成元只将最小的存入。

所以步骤可以归纳为：

• 第一步：建立生成元数组
• 第二步：查表即可

代码

在vs2017上运行通过

#include <stdio.h>
#include <string.h>
#define maxn 100005

int ans[maxn];

int main()
{
    memset(ans, 0, sizeof(ans));  //置为0表示不存在生成元

    //建立生成元数组
    for (int i = 0; i < maxn; i++)
    {//求i是那个数字所对应的生成元（y）
        int x = i, y = i;
        while (x)
        {
            y += x % 10;
            x /= 10;
        }

        if (ans[y] == 0 || ans[y] > i) ans[y] = i;  // 因为要求最小生成元
    }

    //查表输出
    int C, n;
    scanf("%d", &C);

    while (C--)
    {
        scanf("%d", &n);
        printf("%d\n", ans[n]);
    }

    return 0;
}