145各位数字的阶乘之和恰好等于其本身： $$1! + 4! + 5! = 1 + 24 + 120 = 145.$$ 取169各位数字阶乘之和得363601，再取其各位数字阶乘之和得1454，再取其各位数字阶乘之和又得169。

事实上，从一个数开始不断取各位数字阶乘之和，最后又能返回这个数的情况十分罕见。

上例中145经过一步返回自身，169经过三步返回自身。经过三步返回自身的只有以下三个数，并且不存在三步以上的情况： \begin{align*} &169 \rightarrow 363601 \rightarrow 1454 \rightarrow 169\\ &871 \rightarrow 45361 \rightarrow 871\\ &872 \rightarrow 45362 \rightarrow 872\\ \end{align*} 不过从任意数开始不断取各位数字阶乘之和最终都会进入循环，例如 \begin{align*} &69 \rightarrow 363600 \rightarrow 1454 \rightarrow 169 \rightarrow 363601 (\rightarrow 1454)\\ &78 \rightarrow 45360 \rightarrow 871 \rightarrow 45361 (\rightarrow 871)\\ &540 \rightarrow 145 (\rightarrow 145)\\ \end{align*} 上例中，从69开始，在第一次出现重复的数1454前共有五项。

从一个小于一百万的数开始，在第一次出现重复的数前最多能得六十项。有多少个小于一百万的数具有这一性质？

本题难度:

解答

这是典型的在内向基环树结构，遍历所有数并缓存已经计算出的链长即可。结果是$402$。

import math
target=1000000
f=[math.factorial(i) for i in range(10)]
d=[0 for i in range(target)]
d[0]=2
s=0
for n in range(target):
    terms=[]
    m=n
    while m not in terms and (m>=target or d[m]==0):
        terms.append(m)
        m=sum(f[int(i)] for i in str(m))
    r=d[m] if m < target else 0
    for i,j in enumerate(terms):
        if j < target:
            d[j]=len(terms)-i+r
    s=s+(d[n]==60)
print s