欧拉项目 | 第74题 | 阶乘链

原题链接
问题描述：
数字145有一个著名的性质：其所有位上数字的阶乘和等于它本身。
1! + 4! + 5! = 1 + 24 + 120 = 145
169不像145那么有名，但是169可以产生最长的能够连接回它自己的数字链。事实证明一共有三条这样的链：
169 → 363601 → 1454 → 169
871 → 45361 → 871
872 → 45362 → 872
不难证明每一个数字最终都将陷入一个循环。例如：
69 → 363600 → 1454 → 169 → 363601 (→ 1454)
78 → 45360 → 871 → 45361 (→ 871)
540 → 145 (→ 145)
从69开始可以产生一条有5个不重复元素的链，但是以一百万以下的数开始，能够产生的最长的不重复链包含60个项。
一共有多少条以一百万以下的数开始的链包含60个不重复项？

我想，这个题几乎没有什么难度吧。我的做法是把每个数字和它对应的下一个值放到一个字典里面。然后从3开始遍历到100万，统计链的长度。
下面是相关的代码：

int count = 0;

Dictionary<int, int> nexts = new Dictionary<int, int>();
for (int i = 1; i < 1000000; i++)
{
    int key = i;
    int value = GetNext(i);
    nexts.Add(key, value);

    while (value > 1000000)
    {
        key = value;
        value = GetNext(key);
        nexts[key] = value;
    }
}

for (int i = 3; i < 1000000; i++)
{
    HashSet<int> numbers = new HashSet<int>();
    int cur = i;
    while (!numbers.Contains(cur))
    {
        numbers.Add(cur);
        cur = nexts[cur];
    }

    if (numbers.Count == 60)
    {
        count++;
    }
}

return count;

private static int GetNext(int i)
{
    int value = i.ToString().Select(c =>
    {
        int m = int.Parse(c.ToString());
        int product = 1;
        for (int j = 2; j <= m; j++)
        {
            product *= j;
        }
        return product;
    }).Sum();

    return value;
}

在一台很弱的虚拟机里面，大概6秒就能得到结果。

其实，我试了一下暴力的算法，大概1分钟就能得到结果。