L2-018 多项式A除以B（python+测试点14分析)-CSDN博客

本文链接：https://blog.csdn.net/kbcl2/article/details/146000721

题目

这仍然是一道关于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

知识点回顾：多项式的除法

我在做这个题的时候都不知道多项式的除法。。。

对于多项式除法，目标是将被除数 f(x) 除以除数 g(x)，并找到商 q(x) 和余数 r(x)，使得：

$f(x)=q(x)\cdot g(x) + r(x)$

其中，余数 r(x) 的次数必须小于除数 g(x) 的次数。具体步骤如下：

设置除法：确定被除数 f(x) 和除数 g(x)。
除法过程：用 f(x) 的最高次项除以 g(x) 的最高次项，得到商 q(x) 的第一项。
乘法和减法：用得到的商的第一项乘以整个除数 g(x)，然后从 f(x) 中减去这个结果，得到新的多项式。
重复过程：用新的多项式重复步骤 2 和 3，直到新的多项式的次数小于除数 g(x) 的次数。
检查余数：当新的多项式的次数小于除数 g(x) 的次数时，这个多项式就是余数 r(x)。
组装商：将所有得到的商的项组合起来，得到最终的商 q(x)。

代码

个人代码，仅供参考

from collections import defaultdict

# 读取输入的两个多项式 A 和 B
f = list(map(int, input().split()))  # 第一个多项式 A
g = list(map(int, input().split()))  # 第二个多项式 B

# 使用 defaultdict 来存储多项式的指数和系数
fx, gx, qx = defaultdict(float), defaultdict(float), defaultdict(float)

# 解析多项式 A 的指数和系数
for i in range(1, len(f), 2):
    fx[f[i]] = f[i + 1]

# 解析多项式 B 的指数和系数
for i in range(1, len(g), 2):
    gx[g[i]] = g[i + 1]

# 多项式除法主循环
while fx and max(fx.keys()) >= max(gx.keys()):  # 当 A 的最高次项大于等于 B 的最高次项时继续
    a, b = max(fx.keys()), max(gx.keys())  # 获取 A 和 B 的最高次项的指数
    qx[a - b] += fx[a] / gx[b]  # 计算商 Q 的当前项，并更新到 qx 中

    # 构造临时多项式 tmp，用于减去 B 乘以当前商项
    tmp = [a - b, fx[a] / gx[b]]
    tmpx = defaultdict(float)
    for k, v in gx.items():
        tmpx[k + tmp[0]] = v * tmp[1]  # B 乘以当前商项

    # 更新 A (fx) 的系数，减去 tmpx 的值
    for k in set(fx.keys()) | set(tmpx.keys()):
        fx[k] = fx[k] - tmpx[k]
        if not fx[k]:  # 如果某项的系数为 0，删除该项
            del fx[k]

# 构造商 Q 的输出结果
qxres = [len(qx.keys())]  # 初始化商 Q 的输出列表，第一项为非零项的个数
for i in sorted(qx.keys(), reverse=True):  # 按指数从高到低排序
    if f'{qx[i]:.1f}' != '0.0' and f'{qx[i]:.1f}' != '-0.0':  # 跳过零系数项
        qxres.append(i)  # 添加指数
        qxres.append(f'{qx[i]:.1f}')  # 添加系数，保留 1 位小数
    else:
        qxres[0] -= 1  # 如果是零系数项，减少非零项的计数

# 如果商 Q 为空，输出特殊形式 `0 0 0.0`
if qxres == [0]:
    qxres.extend([0, '0.0'])

# 输出商 Q
print(*qxres)

# 构造余数 R 的输出结果
fxres = [len(fx.keys())]  # 初始化余数 R 的输出列表，第一项为非零项的个数
for i in sorted(fx.keys(), reverse=True):  # 按指数从高到低排序
    if f'{fx[i]:.1f}' != '0.0' and f'{fx[i]:.1f}' != '-0.0':  # 跳过零系数项
        fxres.append(i)  # 添加指数
        fxres.append(f'{fx[i]:.1f}')  # 添加系数，保留 1 位小数
    else:
        fxres[0] -= 1  # 如果是零系数项，减少非零项的计数

# 如果余数 R 为空，输出特殊形式 `0 0 0.0`
if fxres == [0]:
    fxres.extend([0, '0.0'])

# 输出余数 R
print(*fxres)