题目描述
给定一个nnn次多项式P(x)=anxn+an−1xn−1+…+a1x+a0P(x) = a_{n}x^{n} + a_{n - 1}x^{n - 1} + \ldots + a_{1}x + a_{0}P(x)=anxn+an−1xn−1+…+a1x+a0的全部n+1n + 1n+1个系数，以及该多项式的n−2n - 2n−2个实根，要求计算出剩下的两个实根。题目保证所有根均为实数，且允许存在重复根。
输入格式
输入的第一行是一个整数kkk，表示待处理的多项式个数。接下来有3×k3 \times k3×k行，每333行为一组，描述一个多项式：
- 第1\texttt{1}1行：一个整数nnn，表示多项式的次数。
- 第2\texttt{2}2行：n+1n + 1n+1个用空格分隔的数值，表示多项式从最高次到最低次的系数。
- 第3\texttt{3}3行：n−2n - 2n−2个用空格分隔的数值，表示该多项式的n−2n - 2n−2个已知实根。
输出格式
输出共2×k2 \times k2×k行，每个多项式对应两行，分别输出两个未知根。每对根必须按递减顺序排列，结果四舍五入保留一位小数。
样例输入
3 3 2 -15 36 -27 3 6 1 -3 -5 15 4 -12 0 1 -2 0 2 3 1 2.3 1 -0.3 -1.5样例输出
3.0 1.5 3.0 -1.0 0.2 -1.0题目分析
多项式除法有一个重要性质：若zzz是多项式P(x)P(x)P(x)的一个根，则(x−z)(x - z)(x−z)整除P(x)P(x)P(x)，即P(x)=(x−z)Q(x)P(x) = (x - z)Q(x)P(x)=(x−z)Q(x)，其中Q(x)Q(x)Q(x)是次数比P(x)P(x)P(x)低111的多项式。利用这一性质，可以逐个消除已知根，把原多项式降阶为二次多项式，再用求根公式解出剩余两个根。
题目已给出n−2n - 2n−2个根，因此只需要进行n−2n - 2n−2次降阶操作，最终得到一个二次多项式a2x2+a1x+a0a_{2}x^{2} + a_{1}x + a_{0}a2x2+a1x+a0。对二次多项式使用求根公式：
x=−b±b2−4ac2a x = \frac{-b \pm \sqrt{b^{2} - 4ac}}{2a}x=2a−b±b2−4ac
即可得到两个未知根。
解题思路
采用Ruffini\texttt{Ruffini}Ruffini法则（综合除法）完成多项式降阶。设当前多项式次数为ddd，系数数组为c0,c1,…,cdc_{0}, c_{1}, \ldots, c_{d}c0,c1,…,cd，已知一个根为rrr。除以(x−r)(x - r)(x−r)后得到的新系数满足递推关系：
cj′=cj+cj−1′×r(j=1,2,…,d−1) c_{j}' = c_{j} + c_{j - 1}' \times r \quad (j = 1, 2, \ldots, d - 1)cj′=cj+cj−1′×r(j=1,2,…,d−1)
其中c0′=c0c_{0}' = c_{0}c0′=c0。在代码实现中，可以直接在原数组上原地更新：从下标111开始，令cj←cj+cj−1×rc_{j} \leftarrow c_{j} + c_{j - 1} \times rcj←cj+cj−1×r。每处理一个根，多项式次数减111。
重复上述过程，直到多项式次数降为222。此时数组中前三个元素即为二次多项式的系数aaa、bbb、ccc。计算判别式Δ=b2−4ac\Delta = b^{2} - 4acΔ=b2−4ac，根据求根公式得到两个根。由于题目要求按递减顺序输出，比较两根大小后依次输出较大者和较小者。
需要注意浮点数比较和精度控制，输出时使用fixed与setprecision(1)保留一位小数。
时间复杂度：每个多项式需要处理n−2n - 2n−2个根，每次降阶遍历当前所有系数，总操作次数为O(n2)O(n^{2})O(n2)。由于题目中nnn规模较小，该复杂度完全足够。
空间复杂度：使用两个定长数组存储系数和根，空间复杂度为O(n)O(n)O(n)。
代码实现
// Polynomial Roots// UVa ID: 930// Verdict: Accepted// Submission Date: 2017-03-14// UVa Run Time: 0.000s//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constdoubleepsilon=1e-7;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases=0;cin>>cases;for(intc=1;c<=cases;c++){intdegree,n;doublecoefficients[100],roots[100];cin>>n;for(inti=0;i<=n;i++)cin>>coefficients[i];n-=2;for(inti=0;i<n;i++)cin>>roots[i];degree=n+2;intidx=0;while(degree>2){for(intj=1;j<degree;j++)coefficients[j]+=coefficients[j-1]*roots[idx];degree--;idx++;}doubleroot1=sqrt(coefficients[1]*coefficients[1]-4.0*coefficients[0]*coefficients[2]);doubleroot2=(-coefficients[1]-root1)/(2.0*coefficients[0]);doubleroot3=(-coefficients[1]+root1)/(2.0*coefficients[0]);if(root2+epsilon<root3)swap(root2,root3);cout<<fixed<<setprecision(1)<<root2<<'\n';cout<<fixed<<setprecision(1)<<root3<<'\n';}return0;}总结
本题的核心是运用多项式除法的基本定理和Ruffini\texttt{Ruffini}Ruffini法则，通过已知根逐步降低多项式次数，最终将问题转化为求解二次方程。实现时直接在系数数组上原地进行综合除法，避免了额外的空间开销。输出时注意按递减顺序排列两个根并保留一位小数。整体思路简洁高效，适合作为多项式运算的入门练习。
