生成元
如果x加上x的各个数字之和得到y，就说x是y的生成元。给出n（1≤n≤100000），求最小 生成元。无解输出0。 例如，n=216，121，2005时的解分别为198，0，1979。
输入演示
3 216 121 2005 （注意：第一行输入代表将要输入的实验数据组数。）
输出演示
198 0 1979
分析
本题看起来是个数学题，实则不然。假设所求生成元为m。不难发现m<n。换句话说， 只需枚举所有的数字m<n，看看有没有哪个数是n的生成元。 可惜这样做的效率并不高，因为每次计算一个n的生成元都需要枚举n-1个数。有没有更快的方法？当然有：只需一次性枚举100000内的所有正整数m，标记“m加上m的各个数字之和得到的数有一个生成元是m”，最后查表即可。
代码展示
#include
<iostream
>
#define maxn
100005
int ans
[maxn
];
using namespace std
;
int
main()
{
int
T, n
;
memset(ans
, 0, sizeof(ans
));
for (int m
= 1; m
<maxn
; m
++)
{
int x
= m
, y
= m
;
while (x
>0)
{
y
+= x
% 10;
x
= x
/ 10;
}
if (ans
[y
] == 0 || ans
[y
]>m
)
{
ans
[y
] = m
;
}
}
cin
>> T;
int
*a
= new int[T];
for (int j
= 0; j
< T; j
++) {
cin
>> n
;
a
[j
] = n
;
}
for (int j
= 0; j
< T; j
++) {
n
= a
[j
];
cout
<< ans
[n
] << endl
;
}
return 0;
}
