l2-018 多项式a除以b (25 分)

题目描述

给定两个多项式 A(x) 和 B(x)，求 A(x) 除以 B(x) 的商和余数。

输入格式

第一行包含一个正整数 n，表示多项式 B(x) 的项数。

第二行包含 n+1 个整数，表示多项式 B(x) 的系数，其中第 i 个整数表示 xi 的系数。

第三行包含一个正整数 m，表示多项式 A(x) 的项数。

第四行包含 m+1 个整数，表示多项式 A(x) 的系数，其中第 i 个整数表示 xi 的系数。

输出格式

第一行输出多项式 A(x) 除以 B(x) 的商的项数。

第二行输出多项式 A(x) 除以 B(x) 的商的系数，其中第 i 个整数表示 xi 的系数。

第三行输出多项式 A(x) 除以 B(x) 的余数的项数。

第四行输出多项式 A(x) 除以 B(x) 的余数的系数，其中第 i 个整数表示 xi 的系数。

多项式的格式为 ax^b，即系数后面跟着 x 的指数，例如 3x^4。

多项式中的系数和指数都是整数，多项式按照指数从高到低排列，如果某项系数为 ，则不输出。

样例输入1

3
3 -1 1 2
4
10 3 -1 2

样例输出1

2
3
1
3 2

样例输入2

2
1 2 1
3
1 4 6 4

样例输出2

2
1 2
1
2

数据范围

1≤n,m≤100
输入样例1：

3
3 -1 1 2
4
10 3 -1 2

输出样例1：

2
3
1
3 2

输入样例2：

2
1 2 1
3
1 4 6 4

输出样例2：

2
1 2
1
2

算法1

(多项式除法) $O(n^2)$

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码