0%

ProjectEuler-356

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

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 有啥想法吗……