题意
原题大体意思是说有一个数 n, 存在一个数 x, x 与上它的每位数的总和等于 n (例: n = 1; x = 15, n = 15 + 1 + 5) .
要求给定一个 n
(
1
<
=
n
<
=
1
0
9
)
(1 <= n <=10^{9})
(1<=n<=109), 求出输出满足条件的 x 个数, 并按升序输出 x 的值.
例1
input
21
output
1
15
Input
20
Output
0
解析
该题其实很简单, 主要是数据范围太大容易超时.
首先, 题中给出了数据范围是
1
<
=
n
<
=
1
0
9
1 <= n <= 10^{9}
1<=n<=109, 也就是说 n 最大为
1
0
9
10^{9}
109, 其次是
1
0
9
−
1
10^{9} - 1
109−1, 我们知道
1
0
9
−
1
10^{9} - 1
109−1这个数每一位都是一个 9, 不难看出 x 的每一位数之和最大就是 9 * 9 也就是 81 ;也就是说如果 n 大于 81, 那么我们只需要循环 n - 81 到 n; 这样就减少了循环量.
剩下的就是用循环依次求取 x 与它的每位的总和与 n 进行比较.
以下是我写的代码:
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1000;
int x[MAXN];//用来统计满足条件的每个 x;
int n, sum, k, a;//sum 每个 x 与它的每位的总和, k 是 x 的个数, a用于循环中的代换;
int main() {
cin >> n;//设置 i 的初始值, 用max()函数判断
for (int i = max(0, n - 81); i < n; i++) {
//用max()函数比较 0 和 (n - 81)的大小, 确定循环的范围;
a = i;
sum = i;// i 代表 x 本身的值;
while (a) {
sum += a % 10; // 加上 x 每一位的值;
a /= 10;
}
if (sum == n) {
k++;
x[k] = i;
}
}
cout << k << endl;//输出结果;
for (int i = 1; i <= k; i++) {
cout << x[i] << ' ';
}
return 0;
}