题目描述

"A fight? Count me in!"
要打架了，算我一个。

"Everyone, get in here!"
所有人，都过来！

冷酷的酒客 (Grim Patron) 对战歌指挥官 (Warsong Commander) 的削弱感到很伤心，他打算用一道数学题来纪念战歌指挥官。

设 $\left\{ u_i \right\}$ 为一数列，满足

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

已知 $u_0, u_1, a, b, c, n$。保证 $x^3 = a x^2 + b x + c$ 有 $3$ 个不同的正整数解。

求 $u_n$。

输入格式

输入仅一行，包含 $6$ 个整数 $u_0, u_1, a, b, c, n$($c \leq 10^5, |u_0|, |u_1| \leq 1000, 0 \leq 10^9$)。

输出格式

输出仅一行，包含一个实数，保留至少 $8$ 位至多 $15$ 位小数。如果你的答案和我们的答案差别不超过 $10^{-6}$，则认为正确。考虑到浮点运算本身的误差，当你的答案与真实答案差别不超过 $10^{-6} - 10^{-8}$ 时，才能保证正确。

题解

可以想到，如果直接暴力计算，大的点会 TLE，小的点还会被卡精度，因此显然不可取。因此，由于注意到 $x^3 = ax^2 + bx + c$ 有三个不同的整根，如果代入 $u_i = u_{i-1} = x$ (那么最终就会有 $u_{i+1} = x$，落入了不动点。

尝试去迭代几次，你就能发现这个数列的值可以迅速收敛到这 (三个) 根之中的一个。因此，对于比较小的 $n$ ($n \leq 60$ 左右)，可以采取使用暴力计算 (由于 double 和 long double 自身的误差，暴力计算的范围不能太大，否则中间会有哪一步突然从一个根跳到另一个根。

而当 $n$ 特别大时 (几百万及以上)，迭代后的值就几乎等于附近的根，因此，我们只需将得到的数进行舍入，然后判断那个整数是否为根即可，如果它是根，那么就直接输出。

有一点要注意的是，要判断它是否有收敛的趋势来判断是否是最后的极限，因为有可能中间经过某个根而不收敛于它 (比如说可以进行最经典的精度判断——即连续两个值距离根的差都不超过 $\epsilon$)。

代码

#include <bits/stdc++.h>
#define N 60
using namespace std;

typedef long long ll;
typedef long double ld;
const ld eps = 1e-10;

int n, a, b, c, i;
ld u[N], rd;

inline bool isroot(ll x) {return ((x - a) * x - b) * x == c;}

int main(){
	scanf("%Lf%Lf%d%d%d%d", u, u + 1, &a, &b, &c, &n);
	if(n > N)
		for(i = 2; i < N; ++i){
			u[i] = (ld)a + ((ld)b + (ld)c / u[i - 2]) / u[i - 1];
			rd = roundl(u[i]);
			if(abs(u[i] - rd) < 0.01 && abs(u[i - 1] - rd) < 0.01)
				if(isroot((ll)rd)) return printf("%.15Lf\n", rd), 0;
		}
	else{
		for(i = 2; i <= n; ++i) u[i] = (ld)a + ((ld)b + (ld)c / u[i - 2]) / u[i - 1];
		printf("%.15Lf\n", u[n]);
	}
	return 0;
}

坑

坑1：注意判断是否收敛的精度，$10^{-2}$ 就够了，太小可能由于浮点精度问题而无法达到。