本题与第76题基本相同，令a(n)为分堆数，d(n)为n的约数和，猜测一个上界（此处用的是60000），再用筛法生成该范围内的d(n)，最后用OEIS A000041中的如下公式
$$a(n)=\frac{1}{n}\sum_{k=0}^{n-1}a(k)d(n-k),$$
可得结果是$n=55374$。
注：本题的时间复杂度很高，需要较长运行时间才能得到结果，最后的$a(55374)$有五百多位。
target=60000
d=[3 if i%2==0 else 1 for i in range(target)]
d[0]=0
n=3
while n < target:
for i in range(n,target,n):
d[i]=(d[i]+n)
n+=1
a=[1,1]
n=1
while n < target-1 and a[n]%1000000:
n+=1
a.append(sum((a[k]*d[n-k]) for k in range(n))/n)
print n
|
