题目描述给定一个nnn次多项式P(x)anxnan−1xn−1…a1xa0P(x) a_{n}x^{n} a_{n - 1}x^{n - 1} \ldots a_{1}x a_{0}P(x)an​xnan−1​xn−1…a1​xa0​的全部n1n 1n1个系数以及该多项式的n−2n - 2n−2个实根要求计算出剩下的两个实根。题目保证所有根均为实数且允许存在重复根。输入格式输入的第一行是一个整数kkk表示待处理的多项式个数。接下来有3×k3 \times k3×k行每333行为一组描述一个多项式第1\texttt{1}1行一个整数nnn表示多项式的次数。第2\texttt{2}2行n1n 1n1个用空格分隔的数值表示多项式从最高次到最低次的系数。第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次降阶操作最终得到一个二次多项式a2x2a1xa0a_{2}x^{2} a_{1}x a_{0}a2​x2a1​xa0​。对二次多项式使用求根公式x−b±b2−4ac2a x \frac{-b \pm \sqrt{b^{2} - 4ac}}{2a}x2a−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′cjcj−1′×r(j1,2,…,d−1) c_{j} c_{j} c_{j - 1} \times r \quad (j 1, 2, \ldots, d - 1)cj′​cj​cj−1′​×r(j1,2,…,d−1)其中c0′c0c_{0} c_{0}c0′​c0​。在代码实现中可以直接在原数组上原地更新从下标111开始令cj←cjcj−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//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constdoubleepsilon1e-7;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases0;cincases;for(intc1;ccases;c){intdegree,n;doublecoefficients[100],roots[100];cinn;for(inti0;in;i)cincoefficients[i];n-2;for(inti0;in;i)cinroots[i];degreen2;intidx0;while(degree2){for(intj1;jdegree;j)coefficients[j]coefficients[j-1]*roots[idx];degree--;idx;}doubleroot1sqrt(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(root2epsilonroot3)swap(root2,root3);coutfixedsetprecision(1)root2\n;coutfixedsetprecision(1)root3\n;}return0;}总结本题的核心是运用多项式除法的基本定理和Ruffini\texttt{Ruffini}Ruffini法则通过已知根逐步降低多项式次数最终将问题转化为求解二次方程。实现时直接在系数数组上原地进行综合除法避免了额外的空间开销。输出时注意按递减顺序排列两个根并保留一位小数。整体思路简洁高效适合作为多项式运算的入门练习。