自动搬运

查看原文

来自洛谷，原作者为

	一只书虫仔 End.

搬运于2025-08-24 22:24:43，当前版本为作者最后更新于2021-05-04 16:59:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Description

给定一个 $n$ 元二次方程：

$$\sum\limits_{i=1}^na_ix_i^2+\sum\limits_{i=1}^{n-1}b_ix_ix_{i+1}=m $$

求 $x_1$ 的范围。

Solution

左侧有 $x_i^2$，右侧又有 $x_ix_{i+1}$，故考虑配方，因为右边的求和式子范围是 $[1,n-1]$，所以先从 $x_{n-1},x_n$ 配起：

$$\begin{aligned}a_{n-1}x_{n-1}^2+b_{n-1}x_{n-1}x_n+a_nx_n^2&=\left(a_{n-1}-\frac{b_{n-1}^2}{4a_n}\right)x_{n-1}^2+\frac{b_{n-1}^2}{4a_n}x_{n-1}^2+b_{n-1}x_{n-1}x_n+a_nx_n^2\\&=\left(a_{n-1}-\frac{b_{n-1}^2}{4a_n}\right)x_{n-1}^2+\left(\frac{b_{n-1}}{2\sqrt{a_n}}+\sqrt{a_n}x_n\right)^2\end{aligned} $$

（Q：为什么调整 $x_{n-1}$ 不调整 $x_n$？A：为了方便求 $x_1$ 的范围而不是 $x_n$ 的范围）

经过配方后，$x_{n-1}^2$ 的系数就从 $a_{n-1}$ 变为了 $a_{n-1}-\frac{b_{n-1}^2}{4a_n}$，那么我们就可以以这个为新的系数，与 $x_{n-2}$ 继续配方，然后以此类推推到 $x_1$，这个过程可以 $\mathcal O(n-1)$ 的倒着循环，最后可以得到 $x_1$ 的系数，设其为 $\alpha$。

$x_1$ 的上下界取于极端情况，即后面 $[x_2,x_n]$ 的加和均为 $0$ 时，即：

$$\begin{aligned}\alpha x_1^2+0&=m\\\alpha x_1^2&=m\\x_1^2&=\frac m \alpha \\x_1&=\pm\sqrt{\frac m \alpha}\end{aligned} $$

$x_1$ 的范围即为：

$$x_1 \in \left[-\sqrt{\frac m \alpha},\sqrt{\frac m \alpha}\right] $$

注意：因为精度问题还是开一下 double 保险，因为这个问题 WA 了好几次。

Code

for (int i = n - 1; i >= 1; i--) {
	double del = (b[i] * b[i]) / (4 * a[i + 1]);
	a[i] -= del;
}
double ans = sqrt(m / a[1]);
if (ans >= 0) printf("%.0f %.0f", -ans, ans);
else printf("%.0f %.0f", ans, -ans);