Project Euler #356 Largest Roots of Cubic polynomials

2019-03-11

三次多项式的最大根

记\(a_n\)为多项式\(g(x) = x^3 – 2^n*x^2 + n\)的最大实根。
例如,\(a_2 = 3.86619826…\)

求$latex \sum _{i=1}^{30} \lfloor a_i^{987654321} \rfloor $的最后\(8\)位数字。


首先这个方程一定有三个实数解,设为\(a,b,c(a>b>c)\),那么我们可以得出

\(a>0,b>0,c<0\),|\(b\)|\(<1\),|\(c\)|\(<1\),|\(b\)|\(>\)|\(c\)|

令\(S(k)=a^k+b^k+c^k\),那么我们可以得出\(S(k)=2^n*S(k-1)-n*S(k-3)\)。

由于\((x-a)*(x-b)*(x-c)=x^3-2^n*x^2+n\),

可以知道\(a+b+c=2^n\),\(a*b+b*c+a*c=0\),所以\(a^2+b^2+c^2=4^n\)

所以可以矩阵快速幂求出来\(S(k)\)。

由于|b|<1,|c|<1,且|b|>|c|,所以\(0<b^k+c^k<1\)

所以\(a^k\)向下取整结果就是\(S(k)-1\)。

P.S.(数学公式坏了,找时间修)

 

 

Leave a Reply:

电子邮件地址不会被公开。 必填项已用*标注