UVa 463 Polynomial Factorization

题目描述

题目要求将给定的整系数四次多项式分解为不可再分的整系数多项式（即素数多项式）的乘积。多项式的系数按降幂顺序给出（从x4x^4x4到常数项）。分解结果要求：

• 每个因子的首项系数为正（最后一个因子除外）。
• 因子按次数升序排列，次数相同时按系数从高次到低次的字典序升序排列。
• 最后输出一个空行。

输入格式

输入包含多行，每行555个整数，表示一个四次多项式的系数（从x4x^4x4到常数项）。第一个系数（x4x^4x4的系数）永远不为负且不为000。输入以文件结束符（EOF\texttt{EOF}EOF）终止。

输出格式

对于每个测试用例，输出若干行，每行表示一个素数因子的系数（从最高次到常数项），因子之间按指定顺序排列，每组输出后跟一个空行。

样例

输入

2 7 -1 -6 -2 2 0 0 0 0

输出

1 -1 2 1 1 4 2 1 0 1 0 1 0 2 0

题目分析

本题的核心是将四次多项式分解为整系数多项式因子的乘积。由于次数固定为444，可能的因子形式包括：

• 一次因子（线性）
• 二次因子
• 四次因子（本身不可再分）

分解策略

1. 尝试提取线性因子：根据有理根定理，如果多项式a4x4+a3x3+a2x2+a1x+a0a_4 x^4 + a_3 x^3 + a_2 x^2 + a_1 x + a_0a4​x4+a3​x3+a2​x2+a1​x+a0​有有理根p/qp/qp/q（既约分数），则ppp整除a0a_0a0​，qqq整除a4a_4a4​。因此，线性因子形式为(qx−p)(q x - p)(qx−p)或(qx+p)(q x + p)(qx+p)。枚举所有可能的ppp和qqq，尝试整除。

2. 尝试二次因子分解：若找不到线性因子，则可能分解为两个二次因子的乘积。设分解形式为：
   (ax2+bx+c)(dx2+ex+f) (a x^2 + b x + c)(d x^2 + e x + f)(ax2+bx+c)(dx2+ex+f)
   其中a⋅d=a4a \cdot d = a_4a⋅d=a4​，c⋅f=a0c \cdot f = a_0c⋅f=a0​。枚举所有可能的a,d,c,fa, d, c, fa,d,c,f（考虑正负因子），然后解线性方程组求出bbb和eee，验证是否为整数且满足多项式恒等。

3. 递归分解：找到一个因子后，对商多项式继续分解，直到所有因子均为素数多项式。

因子排序

分解完成后，对所有因子进行排序：

• 首先按次数升序。
• 次数相同时，按系数向量（从高次到低次）的字典序升序。

首项系数归一化

每个因子的首项系数应为正（最后一个因子除外）。若首项为负，可将整个因子乘以−1-1−1，同时调整最后一个因子的符号以保持乘积不变。

复杂度分析

枚举线性因子时，a4a_4a4​和a0a_0a0​的因子数量有限，每次除法检查O(4)O(4)O(4)次操作。二次因子枚举也有限。整体复杂度可接受。

代码实现

// Polynomial Factorization// UVa ID: 463// Verdict: Accepted// Submission Date: 2025-10-07// UVa Run Time: 0.080s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;/** * 多项式除法：判断多项式a是否能被多项式b整除 * @param a 被除多项式（系数向量，高次在前） * @param b 除多项式（系数向量，高次在前） * @param q 商多项式（输出参数） * @return 如果可整除返回true，否则返回false */booldivisible(vector<int>a,vector<int>b,vector<int>&q){q.clear();// 模拟多项式长除法过程for(inti=0;i+b.size()<=a.size();i++){// 检查当前最高次项是否能整除if(a[i]%b[0])returnfalse;// 计算商的一项intr=a[i]/b[0];q.push_back(r);// 从被除数中减去商乘以除数的结果for(intj=0;j<b.size();j++)a[i+j]-=r*b[j];}// 检查余数是否为零（完全整除）for(intx:a)if(x)returnfalse;returntrue;}/** * 获取一个整数的所有因子（正因子） * @param n 输入整数 * @param f 因子列表（输出参数） */voidgetFactors(intn,vector<int>&f){f.clear();// 遍历1到sqrt(n)寻找因子for(inti=1;i*i<=n;i++){if(n%i==0){f.push_back(i);// 小因子f.push_back(n/i);// 对应的配对因子}}}// 比较函数：按绝对值升序排序boolcmpValue(inta,intb){returnabs(a)<abs(b);}// 比较函数：多项式排序（先按次数升序，次数相同按字典序）boolcmpPoly(vector<int>a,vector<int>b){returna.size()!=b.size()?a.size()<b.size():a<b;}/** * 深度优先搜索分解多项式 * @param d 当前多项式的次数 * @param in 当前要分解的多项式系数 * @param out 分解结果（输出参数） * @return 是否成功分解 */booldfs(intd,vector<int>in,vector<vector<int>>&out){// 基本情况：次数为1，无法再分解if(d==1){out.push_back(in);returntrue;}vector<int>p,q,r;// 获取首项系数和常数项的所有因子getFactors(in[0],p);// 首项系数的因子getFactors(abs(in.back()),q);// 常数项的因子（取绝对值）// 为常数项因子添加负值版本（因为根可能是负数）intqsize=q.size();for(inti=0;i<qsize;i++)q.push_back(-q[i]);if(in.back()==0)q.push_back(0);// 处理常数项为零的情况// 按绝对值排序，优先尝试绝对值小的因子（提高效率）sort(p.begin(),p.end(),cmpValue);sort(q.begin(),q.end(),cmpValue);// 尝试所有可能的线性因子 (a1*x + c1)for(inta1:p)for(intc1:q){vector<int>t={a1,c1};// 构造线性因子if(divisible(in,t,r)){// 检查是否能整除out.push_back(t);// 将因子加入结果returndfs(d-1,r,out);// 递归分解商式}}// 如果次数较低（2或3）且找不到线性因子，直接返回原多项式if(d<=3){out.push_back(in);returntrue;}// 对于4次多项式，尝试二次因子分解 (a1*x² + b1*x + c1)(a2*x² + b2*x + c2)for(inta1:p)for(intc1:q){inta2=in[0]/a1,c2=in.back()/c1;// 计算配对系数// 根据多项式乘法展开，建立方程组：// 原多项式: a0*x⁴ + a1*x³ + a2*x² + a3*x + a4// 分解形式: (a1*x² + b1*x + c1)(a2*x² + b2*x + c2)// 展开后系数对应关系：// x⁴: a1*a2 = a0// x³: a1*b2 + a2*b1 = a1// x²: a1*c2 + b1*b2 + a2*c1 = a2// x¹: b1*c2 + b2*c1 = a3// x⁰: c1*c2 = a4// 从x³和x¹的方程中解出b1和b2// 设方程为：a2*b1 + a1*b2 = a1 (x³系数)// c2*b1 + c1*b2 = a3 (x¹系数)// 这可以看作关于b1, b2的线性方程组intaa=-a2,bb=in[1];// 系数矩阵参数intcc=-(a1*in[2]-a1*a1*c2-a2*c1*a1);// 计算判别式参数// 计算判别式intdelta=bb*bb-4*aa*cc;if(delta<0)continue;// 无实数解inthh=sqrt(delta+0.5);// 开方（加0.5用于四舍五入）if(hh*hh!=delta)continue;// 检查是否为完全平方数// 尝试两个可能的根（正负两个解）for(intsign=-1;sign<=1;sign+=2){// 检查解是否为整数if((sign*hh-bb)%(2*aa))continue;intb1=(sign*hh-bb)/(2*aa);// 计算b1// 从x³方程计算b2，检查是否为整数if((in[1]-b1*a2)%a1)continue;intb2=(in[1]-b1*a2)/a1;// 验证x¹系数方程if(b1*c2+b2*c1!=in[3])continue;// 找到有效的二次因子分解out.push_back({a1,b1,c1});out.push_back({a2,b2,c2});returntrue;}}// 无法分解，返回原多项式out.push_back(in);returnfalse;}intmain(){cin.tie(0);ios::sync_with_stdio(false);// 加速IOinta,b,c,d,e;while(cin>>a>>b>>c>>d>>e){// 读取5个系数（4次多项式）vector<int>in={a,b,c,d,e};// 如果首项系数为负，整体取反（保证首项系数为正）boolreversed=in[0]<0;if(reversed)for(int&x:in)x*=-1;// 分解多项式vector<vector<int>>out;dfs(4,in,out);// 计算所有因子的最大公约数，用于归一化系数intg=1;for(auto&poly:out){inttmpg=0;// 计算当前多项式的系数的GCDfor(intx:poly)if(x)tmpg=tmpg?__gcd(tmpg,abs(x)):abs(x);if(!tmpg)tmpg=1;// 处理全零情况g*=tmpg;// 将当前多项式系数除以GCD进行归一化for(int&x:poly)x/=tmpg;}// 如果之前取反过，现在将整体符号调整回来if(reversed)g=-g;// 对因子排序：先按次数升序，次数相同按字典序sort(out.begin(),out.end(),cmpPoly);// 将整体符号乘到最后一个因子上for(int&x:out.back())x*=g;// 输出结果for(auto&poly:out){for(autoit=poly.begin();it!=poly.end();++it){cout<<*it;if(next(it)!=poly.end())cout<<" ";// 空格分隔，最后无空格}cout<<"\n";}cout<<"\n";// 每个测试用例后输出空行}return0;}