如果一个数 的各位数字之和再加上 ,得到新数 ,那么称 是 的数字生成元。
例如,256 的生成器是 245(245+2+4+5=256)
现在,给你一个数,让你求出它的最小的数字生成器。
输入第一行表示 ,后面的 行的每一行表示一个数字。
输出答案,每个答案以换行隔开。
3 216 121 2005
198 0 1979
方法一:假设所求生成元记为m,不难发现m<n。换句话说,只需枚举所有的m<n,看看有木有哪个数是n的生成元。此举效率不高,因为每次计算一个n的生成元都需要枚举n-1个数。(很明显会超时) 方法二:一次性枚举 100000 内的所有正整数到数组中,最后查表即可。