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
解题思路
我中学数学没学好，开始做道题的时候，不知道要多项式的除法是如何运算的，中学天天混日子无疑 。
主要是参考了柳婼的博客，L2-018. 多项式A除以B -PAT团体程序设计天梯赛GPLT。详细解释就看柳婼小姐姐的吧，我就不班门弄斧了，(ノへ￣、)。
/* 一切都是命运石之门的选择 El Psy Kongroo */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<cmath>
#include<functional>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<double, double> pdd;
typedef pair<string, int> psi;
typedef __int128 int128;
#define PI acos(-1.0)
#define eps 1e-6
#define x first
#define y second
//int dx[4] = {1, -1, 0, 0};
//int dy[4] = {0, 0, 1, -1};
const int inf = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 3010;
int n, m, maxa, maxb;
double a[N], b[N], c[N];
int cntpos(double num[], int high){
int cnt = 0;
for(int i = high; i >= 0; i -- )
if(abs(num[i]) + 0.05 >= 0.1) cnt ++ ;
return cnt;
}
void show(double num[], int high){
int nn = cntpos(num, high);
printf("%d", nn);
if(!nn) {
printf(" 0 0.0");
return;
}
for(int i = high; i >= 0; i -- )
if(abs(num[i]) + 0.05 >= 0.1)
printf(" %d %.1lf", i, num[i]);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
//读入 a 和 b 的系数
scanf("%d", &n);
for(int i = 0; i < n; i ++ ){
int t; scanf("%d", &t);
maxa = max(maxa, t);
scanf("%lf", &a[t]);
}
scanf("%d", &m);
for(int i = 0; i < m; i ++ ){
int t; scanf("%d", &t);
maxb = max(maxb, t);
scanf("%lf", &b[t]);
}
int t1 = maxa, t2 = maxb;
while(t1 >= t2){
double cur = a[t1] / b[t2]; //c系数
c[t1 - t2] = cur;
for(int i = t1, j = t2; j >= 0; i -- , j -- )
a[i] -= b[j] * cur; //b[i - (t1 - t2)] 即 b[j]
while(abs(a[t1]) < eps) t1 -- ;
}
show(c, maxa - maxb);
printf("\n");
show(a, t1);
return 0;
}