水仙数,阿姆斯特朗数,求水仙数的高效算法,求阿姆斯特朗数的高效算法-太阳成集团tyc151cc

using system;
using system.collections.generic;
using system.linq;
using system.text;
using system.numerics;
class program
{
    private static biginteger[] powerof10;
    private static biginteger[,] pretable;
    private static biginteger[,] pretable2;
    private static int[,] pretable3;
    private static int[] selected = new int[10];
    private static int length;
    private static int count = 0;
    public static void main()
    {
        datetime begin = datetime.now;
        for (int i = 1; i < 40; i  )
        {
            initpre(i);
            search(9, 0, i);
        }
        console.writeline(datetime.now - begin);
    }
    private static void initpre(int n)
    {
        powerof10 = new biginteger[n   1];
        powerof10[0] = 1;
        length = n;
        for (int i = 1; i <= n; i  )
            powerof10[i] = powerof10[i - 1] * 10;
        pretable = new biginteger[10, n   1];
        pretable2 = new biginteger[10, n   1];
        pretable3 = new int[10, n   1];
        for (int i = 0; i < 10; i  )
        {
            for (int j = 0; j <= n; j  )
            {
                pretable[i, j] = biginteger.pow(i, n) * j;
                pretable2[i, j] = powerof10[length - 1] - pretable[i, j];
                for (int k = n; k >= 0; k--)
                {
                    if (powerof10[k] < pretable[i, j])
                    {
                        pretable3[i, j] = k;
                        break;
                    }
                }
            }
        }
    }
    private static bool precheck(int currentindex, biginteger sum, int remaincount)
    {
        if (sum < pretable[currentindex, remaincount])
            return true;
        biginteger max = sum   pretable[currentindex, remaincount];
        max /= powerof10[pretable3[currentindex, remaincount]];
        sum /= powerof10[pretable3[currentindex, remaincount]];
        while (max != sum)
        {
            max /= 10;
            sum /= 10;
        }
        if (max == 0)
            return true;
        int[] counter = getcounter(max);
        for (int i = 9; i > currentindex; i--)
            if (counter[i] > selected[i])
                return false;
        for (int i = 0; i <= currentindex; i  )
            remaincount -= counter[i];
        return remaincount >= 0;
    }
    private static void search(int currentindex, biginteger sum, int remaincount)
    {
        if (sum >= powerof10[length])
            return;
        if (remaincount == 0)
        {
            if (sum >= powerof10[length - 1] && check(sum))
            {
                count  ;
                console.writeline("{0}. {1}", count, sum);
                
            }
            return;
        }
        if (!precheck(currentindex, sum, remaincount))
            return;
        if (sum < pretable2[currentindex, remaincount])
            return;
        if (currentindex == 0)
        {
            selected[0] = remaincount;
            search(-1, sum, 0);
        }
        else
        {
            for (int i = 0; i <= remaincount; i  )
            {
                selected[currentindex] = i;
                search(currentindex - 1, sum   pretable[currentindex, i], remaincount - i);
            }
        }
        selected[currentindex] = 0;
    }
    private static bool check(biginteger sum)
    {
        int[] counter = getcounter(sum);
        for (int i = 0; i < 10; i  )
        {
            if (selected[i] != counter[i])
                return false;
        }
        return true;
    }
    public static int[] getcounter(biginteger value)
    {
        int[] counter = new int[10];
        char[] sumchar = value.tostring().tochararray();
        for (int i = 0; i < sumchar.length; i  )
            counter[sumchar[i] - '0']  ;
        return counter;
    }
 
}