P6863 题解
一只书虫仔
·
·
题解
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。
$$\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
```cpp
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);
```