0374 整数分拆积
* * * *
拉格朗日计划
* * * *
整数分拆积

整数n的一个分拆是指将其分割为不减序列之和的一种分割方法。

整数n的一个不等分拆是指将其分割后的各项均不相同。

例如$5=1+1+3$是5的一个分拆,但不是不等分拆,而 $5=1+4=2+3$都是5的不等分拆。注意$5=5$也是5的一个不等分拆,其中只有一项。

记$f(n)$为n的所有不等分拆中各项之积的最大值,并记m(n)为相应的分拆中的项数。例如$f(5)=6$且$m(5)=2$,以及$f(10)=30$且$m(10)=3$(对应$10=2+3+5$)。

可以验证$\sum_{n=1}^{100}f(n)m(n)=1683550844462$。

求$\sum_{n=1}^{10^{14}}f(n)m(n)$模982451653(第五千万个素数)的余数。

本题难度:



解答

首先可以注意到一些一般性的规律:

若分拆中包含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