首先可以注意到一些一般性的规律:
若分拆中包含1和x且不含$1+x$,那么将其替换为$1+x$可以使乘积更大。
若分拆中包含$x < y$且不含$x+1$和$y-1$,那么将其替换为$x+1$和$y-1$可以使乘积更大。
若分拆中包含$x>4$且不含$x-2$,那么将其替换为$2$和$x-2$可以使乘积更大。
反复运用上述几条规律,可以看出对任意给定的n,都存在某个k,能使乘积最大的分拆或者由2到k之间或3到k之间所有的数组成,或者跳过其中至少一个数。
k的具体值可由三角形数(前若干个自然数的和)确定,特别地,当n是三角形数减2的形式时,分拆从3开始且跳过$k-1$。
合并计算即可得结果$334420941$。
target=10**14
bound=14142136
mod=982451653
fact=[1,1]
while len(fact)<=bound:
fact.append((fact[-1]*len(fact))%mod)
a=[bound-2]
for i in range(bound,2,-1):
a.append((a[-1]*i+i-3)%mod)
b=[bound-3]
for i in range(bound-1,2,-1):
b.append((b[-1]*i+i-3)%mod)
s,k=1,2
while (k+1)*(k+2)/2-2<=target:
s=(s+(k-1)*(k+2)/2*fact[k])%mod
k+=1
t=bound*(bound+1)/2-1
for k in range(1,bound):
s=(s+fact[k]*(a[-k] if t-k-1<=target else b[-k]))%mod
print s
|