ProjectEuler 356 - Largest roots of cubic polynomials

好久没做题了似乎，最近被抽代虐的有点发慌。

Problem

令 \(a_n\) 为 \(x^3 - 2^n x^2 + n = 0\) 最大的一个实数根，求 \[\sum_{i=1}^{30} \lfloor {a_i^{987654321}} \rfloor\]

Solution

初看起来不会做……后来一想，指数这么大肯定是有规律的。

对于无理数取整操作来说，比较常用的一种方法是加上一个小于 1 的数，凑成一个整数。要求凑出来的这个整数还是可线性递推求出来的。在这个题目中，把这个方程的几个根打出来看看就会发现一个根很大（理性可以感受到是 \(2^n\) 左右的），另外两个根非常小，绝对值都小于 1 。

对于 \(n\) ，我们不妨设三个根分别为 \(a, b, c\) 。一种很自然的想法就是考虑 \(S_k = a^k + b^k + c^k\) 是否是整数以及是否可递推。递推公式很明显： \[S_{k+1} = 2^n S_k - n S_{k - 2}\]

现在考虑是否为整数的问题。我们只需考虑 \(S_0, S_1, S_2\) 就好了。显然 \(S_0 = 3\) 。由于 \(a, b, c\) 是方程的三个根，可以得到 \((x - a)(x - b)(x - c) = x^3 - 2^n x^2 + n\) ，展开得到 \(a + b + c = 2^n, ab + bc + ca = 0\) 。所以 \(S_1 = 2^n, S_2 = S_1^2 - 2(ab + bc + ca) = 4^n\) ，都是整数。

然后，矩阵乘法就交给 sage 吧～

@dyh 你对 438 有啥想法吗……