[数据结构与算法]天梯赛L2-018 多项式A除以B

链接

题目描述：

这仍然是一道关于 $A/B$ 的题，只不过 $A$ 和 $B$ 都换成了多项式。你需要计算两个多项式相除的商 $Q$ 和余 $R$，其中 $R$ 的阶数必须小于 $B$ 的阶数。

输入格式：

输入分两行，每行给出一个非零多项式，先给出 $A$，再给出 $B$。每行的格式如下：

N e[1] c[1] … e[N] c[N]

其中 $N$ 是该多项式非零项的个数，$e[i]$ 是第 $i$ 个非零项的指数，$c[i]$ 是第 $i$ 个非零项的系数。各项按照指数递减的顺序给出，保证所有指数是各不相同的非负整数，所有系数是非零整数，所有整数在整型范围内。

输出格式：

分两行先后输出商和余，输出格式与输入格式相同，输出的系数保留小数点后 $1$ 位。同行数字间以 $1$ 个空格分隔，行首尾不得有多余空格。注意：零多项式是一个特殊多项式，对应输出为 0 0 0.0 。但非零多项式不能输出零系数（包括舍入后为 $0.0$ ）的项。在样例中，余多项式其实有常数项 $?1/27$，但因其舍入后为 $0.0$，故不输出。

输入样例：

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

输出样例：

3 2 0.3 1 0.2 0 -1.0
1 1 -3.1

思路：

开数组模拟手算除法的过程。输入时记录下 $A$ 与 $B$ 的最高项系数 $n$ 与 $m$，那么商的首项系数就是 $n?m$。之后就是不断地取商，$A$ 减去加权位移后的 $B$。

题面没给最高项的范围，第一次开了 $10^3$ 的数组，RE了一个测试点。改成 $10^4$ 就好了。

#include<bits/stdc++.h>
using namespace std;
const int N=10010;
const double eps=1e-6;
double a[N],b[N],c[N],d[N];
int n,m,num,e[N];

void out(double (&a)[N]){
	num=0;
	for(int i=max(n,m);i>=0;i--) a[i]=round(a[i]*10)/10;
	for(int i=max(n,m);i>=0;i--) if(abs(a[i])>eps) d[++num]=a[i],e[num]=i;
	if(num==0){ cout<<"0 0 0.0\n"; return; }
	cout<<num;
	for(int i=1;i<=num;i++) cout<<fixed<<setprecision(1)<<" "<<e[i]<<" "<<d[i];
	cout<<"\n";
}

void in(double (&a)[N],int &n){
	int t; cin>>t;
	for(int i=1;i<=t;i++){
		int ta; double tb;
		cin>>ta>>tb;
		a[ta]=tb;
		n=max(n,ta);
	}
}

int main(){
	in(a,n),in(b,m);
	for(int i=n-m;i>=0;i--){		//divide
		if(abs(a[i+m])<eps) continue;
		c[i]=a[i+m]/b[m];
		for(int j=m;j>=0;j--) a[i+j]-=b[j]*c[i];
	}
	out(c),out(a);
}