#533. 「例题3-5」生成元( Digit Generator ) 普及/提高−

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

如果一个数 的各位数字之和再加上 ,得到新数 ,那么称 的数字生成元。

例如,256 的生成器是 245(245+2+4+5=256)

现在,给你一个数,让你求出它的最小的数字生成器。

输入格式

输入第一行表示 ,后面的 行的每一行表示一个数字。

输出格式

输出答案,每个答案以换行隔开。

样例

样例输入

3
216 
121 
2005 

样例输出

198 
0 
1979

数据范围与提示

提示

方法一:假设所求生成元记为m,不难发现m<n。换句话说,只需枚举所有的m<n,看看有木有哪个数是n的生成元。此举效率不高,因为每次计算一个n的生成元都需要枚举n-1个数。(很明显会超时)
方法二:一次性枚举 100000 内的所有正整数到数组中,最后查表即可。