0438 根的整数部分
* * * *
拉格朗日计划
* * * *
根的整数部分

给定整数n元组$t=(a_1,\ldots,a_n)$,记$S(t)=|a_1|+\ldots+|a_n|$。

设$x_1\le\ldots\le x_n$是$x^n+a_1x^{n-1}+a_2x^{n-2}+\ldots+a^{n-1}x+a_n=0$的根。

考虑能满足$x_1,\ldots, x_n$均为实数且$\lfloor x_i\rfloor = i$的t,当$n=4$时,有12个这样的t,其$S(t)$之和是2087。

求$n=7$时这样的t的$S(t)$之和。

本题难度:



解答

本题十分繁琐,以下解法概要和代码改编自官方论坛:

记$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