python编程实现广义的多项式Euclid除法

为了实现广义的多项式Euclid除法，我们需要使用拓展欧几里得算法。下面是Python代码实现：

def poly_gcd(a, b):
    """
    计算两个多项式的最大公因式
    :param a: 多项式a
    :param b: 多项式b
    :return: 最大公因式
    """
    if len(b) > len(a):
        a, b = b, a
    r0, r1 = a, b
    s0, s1 = [1] + [0] * (len(a) - 1), [0] * (len(a) - len(b)) + [1] + [0] * (len(b) - 1)
    t0, t1 = [0] * (len(a) - len(b)) + [1] + [0] * (len(b) - 1), [0] * (len(a) - 1) + [1]
    while r1 != [0]:
        q, r2 = poly_div(r0, r1)
        s2 = poly_sub(s0, poly_mul(q, s1))
        t2 = poly_sub(t0, poly_mul(q, t1))
        r0, r1 = r1, r2
        s0, s1 = s1, s2
        t0, t1 = t1, t2
    return r0, s0, t0


def poly_div(a, b):
    """
    计算多项式a除以多项式b的商和余数
    :param a: 多项式a
    :param b: 多项式b
    :return: 商和余数
    """
    if len(b) > len(a):
        return [0], a
    q = [0] * (len(a) - len(b) + 1)
    r = a
    for i in range(len(q)):
        q[-i - 1] = r[-1] / b[-1]
        r = poly_sub(r, poly_mul(q[-i - 1:] + [0] * i, b))
    return q, r


def poly_add(a, b):
    """
    计算两个多项式的和
    :param a: 多项式a
    :param b: 多项式b
    :return: 和
    """
    if len(b) > len(a):
        a, b = b, a
    return [a[i] + b[i - len(a) + len(b)] if i >= len(a) - len(b) else a[i] for i in range(len(a))]


def poly_sub(a, b):
    """
    计算两个多项式的差
    :param a: 多项式a
    :param b: 多项式b
    :return: 差
    """
    if len(b) > len(a):
        a, b = b, a
    return [a[i] - b[i - len(a) + len(b)] if i >= len(a) - len(b) else a[i] for i in range(len(a))]


def poly_mul(a, b):
    """
    计算两个多项式的积
    :param a: 多项式a
    :param b: 多项式b
    :return: 积
    """
    c = [0] * (len(a) + len(b) - 1)
    for i in range(len(a)):
        for j in range(len(b)):
            c[i + j] += a[i] * b[j]
    return c

其中，`poly_gcd`函数计算两个多项式的最大公因式，`poly_div`函数计算多项式a除以多项式b的商和余数，`poly_add`函数计算两个多项式的和，`poly_sub`函数计算两个多项式的差，`poly_mul`函数计算两个多项式的积。