紫薯P52 例题3-5

一、题意

已知 y = x + sum(x的各位数字) (1 <= y <= 100000)
有kase组数据，每组给出一个数字y，要求输出对应的最小x。

二、解析

由于y有大小限制，所以容易得出x最多比y小 5*9=45,因此对于每个y枚举比它小的44个数字即可.

三、代码

#include <iostream>
#include <cmath>
using namespace std;
int kase, n;

int num_sum(int x) {
    int res = 0;
    while(x) {
        res += x % 10;
        x /= 10;
    }
    return res;
}

int solve(int n) {
    for(int i = max(0, n - 45); i < n; i ++) {
        if(n == i + num_sum(i)) return i;
    }
    return 0;
}

int main() {
    cin >> kase;
    while(kase --) {
        cin >> n;
        cout << solve(n) << endl;
    }
}

/*
3
216
121
2005
*/

四、归纳

  • 数学题不要慌，先仔细思考清楚！
  • 看到紫薯给的思路是刷表法，即枚举x从1到100000所有数字，然后维护出能算出y的所有x的最小值。从这里可以学习到，对于有明确一对一的数字关系时，有时可以反过来思考。

果然和紫薯的思考方式永远不一样233