题目要求：

水仙花数（Narcissistic number），它是指一个 n 位数（n≥3 ），它的每个数位上的数字的 n 次幂之和，等于它本身（例如：1³ + 5³+ 3³ = 153）。现给出位数 n ，试求出所有满足条件的水仙花数。

---

听起来是不是很简单？！
我循环遍历所有数字，对每数字每一位进行处理，加起来判断一下不就完了么，还有什么难度？就这？！
那么就来看看计算量有多恐怖吧。

public class Main {public static void main(String[] args) {int n = new Scanner(System.in).nextInt();long starttime = System.currentTimeMillis();fun(n);System.out.println("运行时间：" + (System.currentTimeMillis() - starttime) + " ms");}public static void fun(int n) {int start = 1, end = 10;for (int i = 1; i < n; i++) {start *= 10;end *= 10;}getNarcissisticNumbersWithin(start, end);}public static void getNarcissisticNumbersWithin(int start, int end) {for (int i = start; i <= end; i++) {if (isNarcissistic(i)) {System.out.println(i);}}}public static boolean isNarcissistic(int number) {int D = getDigit(number);int sum = getSum(number, D);return sum == number;}public static int getDigit(int number) {int digit = 1;while ((number /= 10) > 0) {digit++;}return digit;}public static int getSum(int number, int D) {int sum = 0;for (int i = 0; i < D; i++) {sum += Math.pow((number % 10), D);number /= 10;}return sum;}
}

代码很简单，就是对按照水仙花数的定义，遍历数字每一位，判断是否符合要求，是则输入，不是则继续循环操作。
下面我放了几张不同位数的计算量。

这是 6 位水仙花数，运行花了 177 ms，还挺快^_^ 。

这是 7 位的水仙花数，运行花了 2044 ms，也不是很慢嘛！

这是 8 位的水仙花数，比刚才多了 1 位，花了23249 ms 。。

可以明显的看到，随着位数的增加，运行耗费的时间也以十倍以上的关系不断增大，这还没有考虑到后续 int 类型数据溢出的情况，不过算到了后面，哪怕是 long 型，也得溢出。

所以要计算21位的水仙花数，我们采用 Java 的 BigInteger 进行大数处理，但这并不能实际解决问题，所以我们需要对算法进行优化。

---

关键点：弱化水仙花数的数值与水仙花数中每一个数字数位的关系，侧重于每个数字在水仙花数数值中出现的次数。
因此我们可以这么来处理：
1. 写一个函数 calcu_21() 计算 0–9 的 21 次方的大数，并用 base[10] 保存
2. 写一个函数 a[10] 对应保存 0–9 十个数字分别出现的次数
3. 写一个函数 f ，负责搜索遍历所有的情况，需要用到递归
4. 最后写一个测试函数 test ，检验是否为水仙花数

public class ex2 {//每个数字21次方public static BigInteger[] base = new BigInteger[10];public static BigInteger calcu_21(int n) {BigInteger a = BigInteger.ONE;for (int i = 0; i < 21; i++) {a = a.multiply(BigInteger.valueOf(n));}return a;}public static void test(int[] a) {BigInteger bn = BigInteger.ZERO;for (int i = 0; i < a.length; i++) {bn = bn.add(base[i].multiply(BigInteger.valueOf(a[i])));}String s = bn.toString();if (s.length() != 21) {return;}int[] b = new int[10];for (int i = 0; i < s.length(); i++) {b[s.charAt(i) - '0']++;}for (int i = 0; i < 10; i++) {if (a[i] != b[i]) {return;}}System.out.println(bn);}/**处理第 k 个，还有 sum 个名额**/public static void f(int[] a, int k, int sum) {if (sum == 0) {test(a);return;}if (k == a.length - 1) {a[k] = sum;f(a, k + 1, 0);return;}for (int i = 0; i <= sum; i++) {a[k] = i;f(a, k + 1, sum - i);a[k] = 0;}}public static void main(String[] args) {long starttime = System.currentTimeMillis();for (int i = 0; i < base.length; i++) {base[i] = calcu_21(i);}//每个数字出现几次int[] a = new int[10];f(a, 0, 21);System.out.println("运行时间：" + (System.currentTimeMillis() - starttime) + " ms");}
}

最后程序运行截图放出来

计算21水仙花数只花了不到 10s
nice (*^▽*)