算法竞赛 例3-5生成元（Digit Generator,ACM/ICPC Seoul 2005,UVa1583）

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

这道题虽然不涉及到复杂的算法，但思想十分重要。
通过while求解x的每一位之和，累加到y上

x = 198
while(x>0)
{
    y += x % 10;
    x /= 10;
}

用数组存放这样一种一一对应的关系：
要求得1～10000每个数(216)的生成元，用数组a[10005]存放1～10000每个数(216)的生成元a[216]=198，（216—>198）。
数组需要先全部初始化为0（因为有的数不存在生成元，需要输出0）（121—>0）；
循环考察的是1～10000（i的生成元一定小于i）每一个数（198）是谁（216)的生成元，如果这个数（216)的生成元（a[216])已经存在（a[216]!=0）则需要与i(216)的上一个生成元（a[216]）比较，保留更小的生成元。

---

//
//  main.c
//  算法
//
//  Created by 赵海博 on 2018/1/27.
//  Copyright © 2018年 赵海博. All rights reserved.
//

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

//输入216 输出198

//216 = 198+1+9+8

int a[maxn]={0};
// a[y]=x 表示y的生成元是x
int main()
{
#ifdef LOCAL
    freopen("/Users/zhaohaibo/Desktop/a.txt","r",stdin);
#endif
    int i;
    //首先求出1～maxn每个数y的生成元x 存入数组a

    for(i=1;i<=maxn;i++)
    {
        //i是原数y，生成元x一定小于y
        int x=i,y=i;  //x=y=198
        while(x>0)
        {
            y += x % 10; //y = 198 +1 ; +9 + 8
            x /= 10; // x = 198 / 10 = 19; 1
        }
        // y = 216  ; x = 198
        if( a[y] == 0 || y < a[i])
            a[y] = i;
    }
    //while(T--) 三个输入输出
    int T,input;
    scanf("%d\n",&T);
    while(T--)
    {
        scanf("%d",&input);
        printf("%d ",a[input]);
    }
    return 0;
}