本题十分繁琐,以下解法概要和代码改编自官方论坛:
记$f_n(x)=x^n+a_1x^{n-1}+a_2x^{n-2}+\ldots+a^{n-1}x+a_n$,若$x_i\neq i$,那么由介值性可得$f_n(i)$与$f_{n+1}(i)$的符号相反,从而得到一些列关于系数$a_k$的等式($x_i=i$时)或不等式。
$a_k$的范围由两种极限情况(韦达定理)$f_n(x)=(x-1)\ldots(x-n)$和$f_n(x)=(x-2)\ldots(x-n-1)$给出,枚举这些系数并检验是否符合上述等式和不等式组。
最后还需检验$f_n$的每个根都是单根,这可以借助Rolle定理通过验证$f_n'$在$x_i$处的符号也交替变化来实现。
最终结果是$2046409616809$。
res=0
f=lambda a1,a2,a3,a4,a5,a6,x:((((((x+a1)*x+a2)*x+a3)*x+a4)*x+a5)*x+a6)*x
df=lambda a1,a2,a3,a4,a5,a6,x:(((((7*x+6*a1)*x+5*a2)*x+4*a3)*x+3*a4)*x+2*a5)*x+a6
sa2=305
sa3=-1960
sa4=6769
for a1 in range(-28,-35,-1):
print "checking a1=",a1,"current sum:",res
if sa2>0:
ta2=sa2+17
se2=sa2=0
for a2 in range(ta2,512):
if se2>0 and a2>se2+1:
break
if sa3 < 0:
ta3=sa3
se3=sa3=0
for a3 in range(ta3,-4026,-1):
if se3 < 0 and a3 < se3-4:
break
if sa4>0:
ta4=sa4-1000
se4=sa4=0
for a4 in range(ta4,18425):
if se4>0 and a4>se4+30:
break
y1,y2,y3,y4,y5,y6,y7,y8=(f(a1,a2,a3,a4,0,0,i) for i in range(1,9))
a5low=max((2*y3-y2-y4)//2,(2*y5-y4-y6)//2,(2*y7-y6-y8)//2,(2*y5-y2-y8)//18)
a5high=min((2*y2-y1-y3)//2,(2*y4-y3-y5)//2,(2*y6-y5-y7)//2,(2*y4-y1-y7)//18)
for a5 in range(a5low,a5high+1):
y1,y2,y3,y4,y5,y6,y7,y8=(f(a1,a2,a3,a4,a5,0,i) for i in range(1,9))
if y2+y4 < 2*y3 or y4+y6 < 2*y5 or y6+y8 < 2*y7 or y2+y8 < 2*y5:
break
if y1+y3>2*y2 or y3+y5>2*y4 or y5+y7>2*y6 or y1+y7>2*y4:
continue
a6=(y1-y6)//5
while True:
y1,y2,y3,y4,y5,y6,y7,y8=(f(a1,a2,a3,a4,a5,a6,i) for i in range(1,9))
up,dn=min(y2,y4,y6,y8),max(y1,y3,y5,y7)
if up>=dn:
for n in (2,4,6):
if f(a1,a2,a3,a4,a5,a6,n)==up and df(a1,a2,a3,a4,a5,a6,n)>=0:
up-=1
if y8==up:
up-=1
for n in (1,3,5,7):
if f(a1,a2,a3,a4,a5,a6,n)==dn and df(a1,a2,a3,a4,a5,a6,n)<=0:
dn+=1
if up>=dn:
se2=sa2=a2
se3=sa3=a3
if sa4==0:
sa4=a4
se4=a4
res+=(-a1+a2-a3+a4-a5+a6+dn)*(up-dn+1)+(up-dn)*(up-dn+1)//2
a6+=1
else:
if y7>y2 or y7>y4 or y7>y6 or y5>y2 or y5>y4 or y3>y2:
break
a6+=1
print res
|