题意分析

1. 题目要求对于给定的每个正整数 \(n\)，找出大于 \(n\)的最小史密斯数并输出。
2. 史密斯数的定义为：一个非质数，其各位数字之和等于它的所有质因数各位数字之和。

解题思路

1. 计算数字各位数字之和：
   • 定义函数 dis(int x)，通过循环将数字 (x) 的每一位数字取出并相加，返回各位数字之和。
2. 分解质因数并计算质因数各位数字之和：
   • 定义函数 pr(int x)，用于分解质因数并计算质因数各位数字之和。
   • 从 \(2\)开始，到 \(\sqrt{x}\) 为止，检查 \(x\) 是否能被当前数 \(i\) 整除。如果能整除，则不断将 \(x\) 除以 \(i\)，并累加 \(i\) 的各位数字之和。
   • 如果循环结束后 \(x\) 等于初始值，说明 \(x\) 是质数，返回 \(-1\)。
   • 如果 \(x\) 大于 \(1\)，说明还有一个大于 \(\sqrt{x}\) 的质因数，将其各位数字之和累加到结果中。
3. 寻找史密斯数：
   • 在 main 函数中，通过循环不断读取输入的整数 \(n\)。
   • 对于每个 \(n\)，从 \(n + 1\) 开始，逐个检查每个整数是否为史密斯数。
   • 调用 pr(int x) 函数获取当前整数的质因数各位数字之和，如果该和等于当前整数的各位数字之和且当前整数不是质数（即 pr(int x) 返回值不为 \(-1\)），则找到了一个史密斯数，输出该数并跳出循环。

复杂度分析

1. 时间复杂度：
   • 对于 dis(int x) 函数，其时间复杂度为 \(O(\log_{10}x)\)，因为循环次数取决于数字 \(x\) 的位数。
   • 对于 pr(int x) 函数，其时间复杂度主要取决于分解质因数的过程。在最坏情况下，需要检查从 \(2\) 到 \(\sqrt{x}\) 的所有数，因此时间复杂度为 \(O(\sqrt{x})\)。
   • 在 main 函数中，对于每个输入的 \(n\)，需要从 \(n + 1\) 开始逐个检查整数是否为史密斯数，直到找到为止。由于题目中未明确输入 \(n\) 的范围，假设输入的 \(n\) 最大为 \(10^8\)，则在最坏情况下，需要检查的整数个数为 \(10^8 - n\)，每个整数都需要调用 dis(int x) 和 pr(int x) 函数，因此总的时间复杂度为 \(O((10^8 - n) \times (\log_{10}x + \sqrt{x}))\)。
2. 空间复杂度：
   • 代码中主要使用了几个整数变量，如 n、t、sum 等，以及函数调用栈，因此空间复杂度为 \(O(1)\)。

代码实现

#include <cstdio>

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

// 分解质因数并计算质因数各位数字之和
int pr(int x)
{
    int sum = 0;
    int t = x;
    for (int i = 2; i * i <= x; i++)
    {
        if (t % i == 0)
        {
            while (t % i == 0)
            {
                sum += dis(i);
                t /= i;
            }
        }
    }
    if (t == x) // 本身是素数
        return -1;
    if (t > 1)
        return sum + dis(t);
    else
        return sum;
}

int main()
{
    int n, t;
    while (~scanf("%d", &n) && n)
    {
        for (int i = n + 1;; i++)
        {
            t = pr(i);
            if (t!= -1 && t == dis(i))
            {
                printf("%d\n", i);
                break;
            }
        }
    }
    return 0;
}