高位水仙花数算法优化

算法思路：
以三位的水仙花数为例——

1. 432各位立方幂和为99，小于100，则不能使用；
2. 433各位立方幂和为118，但118并不由4 3 3三个数组成，则不是水仙花数；
3. 531各位立方和为153，且153由5 3 1组成，则是水仙花数；
4. 777各位立方和为1029，大于999，则不能使用，结束循环。

再通过预处理（初始化0~9的N次幂）+递归减少运算量。
直接看代码吧：

import java.math.BigInteger;

/**
 * @class: Narcissistic
 * @author: Chitose
 * @date: 2018/11/11
 * @description:
 */

public class Narcissistic  {

    public static int size = 21;
    public static BigInteger powArray[] = new BigInteger[10]; // 记录0~9的size次方
    public static int usedTimes[] = new int[10];// 记录0~9的使用次数
    public static BigInteger powArrayTimes[][]; //记录0到9中任意数字i的N次方乘以其出现的次数j的结果（i^N*j）
    public static BigInteger MAX; // size位的数字能表示的最大值
    public static BigInteger MIN; // size位的数字能表示的最小值


    public static void main(String[] args) {

        long start = System.currentTimeMillis();

        for (int i = 0; i < 10; i++) {// 初始化powArray[]
            powArray[i] = (new BigInteger("" + i)).pow(size);
        }
        MIN = BigInteger.valueOf(10).pow(size - 1); // 初始化最小值
        MAX = BigInteger.valueOf(10).pow(size);     // 初始化最大值（不能等于这个值）

        powArrayTimes = new BigInteger[10][size + 1];  //初始化powArrayTimes[][]
        for (int i = 0; i < 10; i++) {
            powArrayTimes[i][0] = BigInteger.valueOf(0);
            for (int j = 1; j < size + 1; j++) {
                powArrayTimes[i][j] = powArrayTimes[i][j - 1].add(powArray[i]);
            }
        }

        solve(9, 0, BigInteger.ZERO);

        long end = System.currentTimeMillis();
        System.out.println(end-start+"毫秒");

    }

//index:当前轮到的0~9数字   used:当前已使用的数字总数   now:当前各数字幂和
    static void solve(int index, int used, BigInteger now){

        if(index == 0){                     //若index到0了则剩下的全部都是0
            usedTimes[0] = size - used;
            solve(-1, size, now);
            usedTimes[0] = 0;
            return;
        }

        if(used == size){
            if(now.compareTo(MIN)<0) {      //若现在值还是小于最小值，退出
                return;
            }
            String strNow = now.toString();
            int realUsedTimes[] = new int[10];                  // 记录真实的数中0~9的使用次数
            for(int i = 0 ; i < strNow.length() ; i++){
                realUsedTimes[strNow.charAt(i)-'0']++;
            }
            for(int i = 0 ; i < 10 ; i++){
                if(realUsedTimes[i] != usedTimes[i]) {          //若比对真实值与使用数不同则退出递归
                    return;
                }
            }
            System.out.println(now);                            //如果0~9的使用次数都相同才打印
            return;
        }

        //递归主要部分
        for(int i = 0 ; i < size - used ; i++){
            if(now.add(powArrayTimes[index][i]).compareTo(MAX)>=0){          //如果已经超过最大值直接退出这一层递归
                return;
            }
            usedTimes[index] = i;       //使用i次index的数
            solve(index-1, used+i, now.add(powArrayTimes[index][i]));
            usedTimes[index] = 0;       //还原使用次数
        }
    }
}

以21位的水仙花数做例子，输出如下：

128468643043731391252
449177399146038697307
4.155秒