判断x是否为a与其各位和的算法问题及C代码故障排查求助

问题描述 #

输入长整数t和x，其中1 ≤ t ≤ 100000，1 ≤ x ≤ 1000000。先读取t的值，接着读取t行x，对于每个x，判断是否存在整数a满足等式 x = a + sum-of-digits(a)（sum-of-digits(a)表示a的各位数字之和），若存在则输出Yes，否则输出No。

示例 #

输入：

2
97
119

输出：

No
Yes

示例说明：t=2，对于97不存在符合条件的a，输出No；对于119，存在a=109满足119=109+1+0+9，输出Yes。

代码错误排查 #

你写的C代码存在多个致命问题，导致无法正常运行：

• scanf格式错误：scanf("%ld ", &t); 和 scanf("%ld ", &x); 中的多余空格会让程序跳过所有空白字符才继续读取输入，批量输入时会出现读取卡住的情况。
• 变量覆盖逻辑混乱：计算各位数字和的循环里，n = r % 10;直接覆盖了外层循环的变量n，导致外层循环的递增逻辑彻底失效。
• 判断条件完全错误：if (x == (sum + x)) 这个等式永远不成立（除非sum=0，但n从1开始，sum至少为1），程序必然只会输出No。
• 效率极低：对每个x从1遍历到1e6，当t=1e5时，时间复杂度完全超标，肯定会超时。

正确解题思路 #

对于每个x，不需要从1开始遍历a的可能值：因为一个6位数的各位数字之和最大是9*6=54，所以a的取值范围只需要是[x-54, x-1]（a必须小于x，且各位和至少为1）。每个x最多只需要检查54次，效率极高，完全能处理t=1e5的场景。

修正后的代码 #

#include <stdio.h>

// 计算数字的各位之和
int sum_digits(long long n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        long long x;
        scanf("%lld", &x);
        int found = 0;
        // 缩小遍历范围，避免无效循环
        long long start = x > 54 ? x - 54 : 1;
        for (long long a = start; a < x; a++) {
            if (a + sum_digits(a) == x) {
                found = 1;
                break;
            }
        }
        printf(found ? "Yes\n" : "No\n");
    }
    return 0;
}

代码说明 #

• 移除了scanf中的多余空格，确保输入读取正常。
• 单独封装sum_digits函数计算各位和，避免变量覆盖问题。
• 把遍历范围缩小到x-54到x-1，大幅提升运行效率。
• 修正判断条件为a + sum_digits(a) == x，逻辑完全正确。

内容的提问来源于stack exchange，提问作者Fateme