求判断一个区间内的水仙花数
首先，需要告诉一下水仙花数是啥呀
然后就碎给定一个区间，要求求区间内的水仙花数有多少个，感觉在某个付费专栏看到过，求一发兄弟们
一、题目描述
循环输入。每组输入为两个数 $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)$ 这里是为了两个输出的数中间加上空格，最后一个数后不加空格，直接回车。