题目描述

设 $u_i$ 为一数列，满足：

$$
u_i = a + \frac{b}{u_{i-1}} + \frac{c}{u_{i-1}u_{i-2}} \quad (i \ge 2)
$$

给定 $u_0, u_1, a, b, c, n$，保证 $x^3 = a x^2 + b x + c$ 有 $3$ 个不同的正整数解，求 $u_n$

其中 $$c \le 100000, |u_0| \le 1000, |u_1| \le 1000, 0 \le n \le 10^9$$

题解

设 $v_i=\prod_{j=1}^{i}u_j$，由于 $u_i = a + \frac{b}{u_{i-1}} + \frac{c}{u_{i-1}u_{i-2}}$，则 $v_i=v_{i-1}(a+\frac{b}{u_i}+\frac{c}{u_{i-1}u_{i-2}})$

化简可得 $v_i=av_{i-1}+bv_{i-2}+cv_{i-3}$

由于 $x^3=ax^2+bx+c$ 有三个不同的根，设它们从大到小为 $\alpha, \beta,\gamma$

则存在实数 $x,y,z$，满足 $v_i=x \alpha^i+y \beta^i + z \gamma^i$

即 $u_i=\frac{v_i}{v_{i-1}}=\frac{x \alpha^i+y \beta^i + z \gamma^i}{x \alpha^{i-1}+y \beta^{i-1} + z \gamma^{i-1}}$

于是它是收敛的，要么高精度要么直接暴力模拟即可……

若 $x=y=0$，极限为 $\gamma$

若 $x=0,y \ne 0$，极限为 $\beta$

若 $x \ne 0$，极限为 $\alpha$