生成元Digit Generator

洛谷UVA1583 点这里查看原题
难度：普及-

备注：以下内容为重新翻译（洛谷这道题翻译的不是很让人满意），原题PDF点击这里查看

题目描述

如果$x$加上$x$的各位数字之和得到$y$，就是说$x$是$y$的“生成元”。例如$245$是$256$的生成元，因为 $245+2+4+5=256$。
有些正整数没有生成元，而有些正整数有不止一个生成元，例如$198$和$207$都是$216$的生成元,而$198$是其中最小的。

你需要写一个程序，计算并输出$t$个整数中每一个的最小生成元。如果一个整数不存在生成元，则对应输出$0$。

输入格式

输入共$t+1$行：

第$1$行, $1$个整数$t$，表示需要求$t$个整数的生成元;

之后的$t$行，每行一个整数$n$,依次为需要求生成元的每个数。

输出格式

输出共$t$行：

你需要依次输出每个整数的生成元，每行一个。

样例 #1

样例输入 #1

3
216
121
2005

样例输出 #1

198 0 1979

提示

对于 $100\%$的数据， $1\le k,n\le 100000$。

答案

#include<bits/stdc++.h>
using namespace std;

int a[100001];

int getsum(int number){
	int sum=0;
	while(number!=0){
		sum += number%10;
		number /= 10;
	}
	return sum;
}

void saveSum(){
	for(int i=100000;i>=1;i--){
		int num = getsum(i);
		a[num+i]=i;
	}
}

int main(){
	int n,t,b[100001];
	saveSum();
	cin >> t;
	for(int i=1;i<=t;i++){
		cin >> n;
		b[i] = a[n];
	}
	for(int i=1;i<=t;i++){
		cout << b[i] << endl;
	}
	return 0;
}