求判断一个区间内的水仙花数

Question

首先，需要告诉一下水仙花数是啥呀
然后就碎给定一个区间，要求求区间内的水仙花数有多少个，感觉在某个付费专栏看到过，求一发兄弟们

Answer 1

一、题目描述

  循环输入。每组输入为两个数 $l$ 和 $r$，要求输出 $[l, r]$ 范围内的所有水仙花数。没有的话输出 no。当没有任何输入时，程序结束。其中，水仙花数的定义如下：
  1）十进制位数有三位；
  2）每一位的立方和等于它本身；

二、解题思路

难度：🔴🔴⚪⚪⚪

• 首先，我们可以利用差分法，如果我们知道 1 到 $n$ 的水仙花数有 $s_n$ 个，那么区间 $[l, r]$ 中的水仙花数个数就是：
• $$s_r - s_{l-1}$$
• 然后，我们可以预处理出 $s_n$ 数组。
• 对于一个数 $n$，判断它是不是水仙花数，只需要提取它的 个位 $x$、十位 $y$、百位 $z$，如下：
• $x$：n % 10；
• $y$：n / 10 % 10；
• $z$：n / 100 % 10；
• 然后利用定义判断 $n$ 和 $x^3+y^3+z^3$ 是否相等即可。

  三、代码详解

  ```c
  #include <stdio.h>

int n, m;
int all[1000];
int val[1000];

int main() {
all[99] = 0;
for (int i = 100; i <= 999; ++i) {
int v0 = i / 100; // (1)
int v1 = i / 10 % 10; // (2)
int v2 = i % 10; // (3)
val[i] = (i == v0v0v0 + v1v1v1 + v2v2v2) ? 1 : 0; // (4)
all[i] = all[i - 1] + val[i]; // (5)
}

while (scanf("%d %d", &n, &m) != EOF && n) {
    int v = all[m] - all[n - 1];     // (6)
    if (!v) {
        printf("no\n");
    }
    else {
        int hasoutput = 0;
        for (int i = n; i <= m; ++i) {
            if (val[i]) {
                if (hasoutput) {     // (7)
                    printf(" ");
                }
                printf("%d", i);
                hasoutput = 1;
            }
        }
        puts("");
    }
}
return 0;

}

```

• $(1)$ 提取百位；
• $(2)$ 提取十位；
• $(3)$ 提取个位；
• $(4)$ 根据定义判断是否是水仙花数，是则计数为1，否则为0；
• $(5)$ 统计水仙花数 $s_n$；
• $(6)$ 差分法配合前缀和；
• $(7)$ 这里是为了两个输出的数中间加上空格，最后一个数后不加空格，直接回车。

四、扩展阅读

【第26题】给定 l 和 r，输出所有 [l, r] 的水仙花数 | 差分法初体验_英雄哪里出来-CSDN博客 难度：★★☆☆☆，差分法初体验 https://blog.csdn.net/WhereIsHeroFrom/article/details/118273107